LeetCode TwoSum问题代码调试求助：无法通过指定测试用例

Hey there! Let's break down why your code isn't working as expected, and fix it step by step.

The Core Issues #

Your current approach has three critical problems:

1. Sorting destroys original indices: Arrays.sort(nums) modifies the array in place, rearranging elements. The left and right pointers you use refer to positions in the sorted array, not the original input—even if you find the correct values, their indices no longer match the original array.
2. Incorrect return value: You're adding 1 to left for no reason, which shifts the index incorrectly (like in the third test case [3,3], this would return [1,1] instead of the correct [0,1]).
3. Wrong loop structure: Using a for-each loop to drive the two-pointer logic is unnecessary—you should use a while loop that runs only while left < right, since the pointers will converge once the solution is found.

Fix 1: Hash Map Approach (Most Efficient) #

This method avoids sorting entirely, keeping track of indices as you go. It runs in O(n) time and uses O(n) space, making it the optimal choice for this problem.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> valueToIndex = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            // Check if we've already seen the complement value
            if (valueToIndex.containsKey(complement)) {
                return new int[]{valueToIndex.get(complement), i};
            }
            // Store current value and its original index
            valueToIndex.put(nums[i], i);
        }
        
        // Per problem statement, a solution always exists—this is just a fallback
        return new int[]{0, 0};
    }
}

Fix 2: Two-Pointer with Preserved Indices #

If you want to stick with the two-pointer approach, you need to keep track of the original indices before sorting. Here's how to adjust your code:

import java.util.Arrays;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Create an array to store each value with its original index
        int[][] indexedNums = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            indexedNums[i][0] = nums[i];
            indexedNums[i][1] = i;
        }
        
        // Sort the array by the value (first element of each pair)
        Arrays.sort(indexedNums, (a, b) -> Integer.compare(a[0], b[0]));
        
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int sum = indexedNums[left][0] + indexedNums[right][0];
            if (sum == target) {
                // Return the original indices stored in the pairs
                return new int[]{indexedNums[left][1], indexedNums[right][1]};
            } else if (sum > target) {
                right--;
            } else {
                left++;
            }
        }
        
        return new int[]{0, 0};
    }
}

Testing the Fixes #

• For test case 2 (nums = [3,2,4], target = 6):
  • The hash map approach will calculate 6 - 4 = 2, which was stored at index 1, so returns [1,2] (correct).
  • The indexed two-pointer approach sorts the pairs to [(2,1), (3,0), (4,2)], finds the sum 2+4=6, and returns the original indices [1,2].

Both fixes will pass all your test cases, including the tricky third one with duplicate values.

内容的提问来源于stack exchange，提问作者kartik04