如何使TwoSum方法在无序整数数组场景下正确运行？

嘿，我看到你用双指针法解决TwoSum时遇到了问题——这个方法确实高效，但它有个关键前提：数组必须是有序的！咱们先看看你的测试用例到底出了什么问题，再给出两种靠谱的解决方案。

问题出在哪？ #

你的代码逻辑是通过调整首尾指针的位置来逼近目标和，但这个逻辑完全依赖数组的升序特性。拿你提到的测试用例nums = [3,2,4]，target = 6来说：

• 初始start=0（对应值3），end=2（对应值4），两者和为7，比目标6大，所以你让end--到1（对应值2）
• 现在start=0，end=1，和为5，比6小，于是start++到1，此时start不再小于end，循环直接退出，根本没机会找到正确的组合（值2和4，对应下标1和2）

解决方案1：排序+双指针（保留原下标） #

如果你想继续用双指针，得先把数组元素和它的原下标绑定在一起，排序后再用双指针查找，最后返回原下标。代码示例如下：

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        // 将每个元素和它的原下标配对，然后按值排序
        var indexedNums = nums.Select((value, index) => new { Value = value, Index = index })
                              .OrderBy(item => item.Value)
                              .ToArray();
        
        int start = 0;
        int end = indexedNums.Length - 1;
        while (start < end) {
            int currentSum = indexedNums[start].Value + indexedNums[end].Value;
            if (currentSum == target) {
                // 返回原下标，顺序不影响题目要求
                return new int[] { indexedNums[start].Index, indexedNums[end].Index };
            } else if (currentSum < target) {
                start++;
            } else {
                end--;
            }
        }
        // 题目明确说输入必有解，这里只是占位
        return new int[2];
    }
}

这种方法的时间复杂度是O(n log n)（主要来自排序），空间复杂度O(n)用于存储带标的数组。

解决方案2：哈希表法（更适合无序数组的最优解） #

对于无序数组，哈希表法是更高效的选择——时间复杂度O(n)，空间复杂度O(n)。核心思路是：遍历数组时，用哈希表记录已经见过的元素值和它的下标，对当前元素计算target - 当前值，如果这个差值在哈希表里存在，那我们就找到了答案！

代码示例：

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> numIndexMap = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];
            // 检查差值是否已经在哈希表中
            if (numIndexMap.ContainsKey(complement)) {
                return new int[] { numIndexMap[complement], i };
            }
            // 先检查再存入，避免重复使用同一个元素
            if (!numIndexMap.ContainsKey(nums[i])) {
                numIndexMap.Add(nums[i], i);
            }
        }
        // 题目保证有解，这里无需处理无解情况
        return new int[2];
    }
}

拿你的测试用例跑一遍：

• 遍历到i=0（值3）：complement=6-3=3，哈希表为空，存入3:0
• 遍历到i=1（值2）：complement=6-2=4，哈希表没有4，存入2:1
• 遍历到i=2（值4）：complement=6-4=2，哈希表存在2:1，直接返回[1,2]，完美命中正确答案！

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