我在 C# leetcode TwoSum 中遇到了逻辑问题。最后一个重复数字的情况返回错误的索引

Question

挑战要求函数应返回两个数字加起来等于目标数字的两个索引。它接收一个数组并返回一个具有两个索引的数组。

我的解决方案：

public int[] TwoSum(int[] nums, int target) {
    var solution = new int[2];   
    var numsTemp = new int[nums.Length];
    Array.Copy(nums, numsTemp, nums.Length);

    for (int index = 0; index < numsTemp.Length; index++) {
        int currentNum = numsTemp[index];

        for (int innerIndex = 0; innerIndex < numsTemp.Length; innerIndex++) {
            if (Array.IndexOf(nums, currentNum) != Array.IndexOf(nums, numsTemp[innerIndex])) {
                int result = currentNum + numsTemp[innerIndex];
                
                if(result == target) {
                    solution[0] = Array.IndexOf(nums, numsTemp[innerIndex]);
                    int next = 0;

                    if(currentNum == numsTemp[innerIndex]) {
                        next = Array.IndexOf(nums, numsTemp[innerIndex]) + 1;
                    }

                    solution[1] = Array.IndexOf(nums, currentNum, next);
                    break;
                }
            }
        }
    }

    return solution;
}

上面的代码适用于其他具有不同数字的情况。但是对于数组

{3, 3}

，它返回错误的索引。

在

if(currentNum == numsTemp[innerIndex])

行中，我更改了

next

变量的“if块”内的值，因此当分配

solution[1]

索引时，代码会查找下一个索引，并且不会再次返回前3个索引，显然它不起作用。有人可以帮我看看出了什么问题吗？

Answer 1

经典的解决方案使用某种哈希表，比如

Dictionary

：

public int[] TwoSum(int[] nums, int target) {
  if (nums is null)
    return new [] {-1, -1};

  Dictionary<int, int> known = new();  

  for (int i = 0; i < nums.Length; ++i) {
    if (known.TryGetValue(target - nums[i], out int index))
      return new [] {index, i};

    known.TryAdd(nums[i], i);
  }

  return new [] {-1, -1};
}

如果要实现嵌套循环解决方案，请注意内部索引必须大于外部索引；在你的代码中它可以是

for (int innerIndex = index + 1; innerIndex < numsTemp.Length; innerIndex++)

代码

public int[] TwoSum(int[] nums, int target) {
  if (nums is null)
    return new [] {-1, -1};

  for (int outer = 0; outer < nums.Length; ++outer)
    for (int inner = outer + 1; inner < nums.Length; ++inner) 
      if (nums[inner] + nums[outer] == target)
        return new [] { outer, inner };

  return new [] {-1, -1};  
}