Leetcode 算法题：Two Sum

题目分析

题目要求在一个给定的数组中，找出数组中两个元素，它们俩的和等于目标值，并且只有一个答案存在。

1. 由于只有一个答案存在，所以返回的答案不能是同一个下标值。即如果目标值是 8，数组中找到了一个元素是 4 的话，就算 8=4+4，也不能直接返回这个 4 的下标两次；
2. 只有一个唯一的答案存在，所以不用考虑太复杂的情况（如不存在答案、存在多个答案等）；
3. 数组的最大长度 10^4，所以需要考虑时间复杂度和空间复杂度上的性能问题。

第一版：暴力解法

暴力接法是最简单的方法，通过双重 for 循环遍历所有的元素组合，找到那一个唯一解即可。

public class TwoSum {  
    public int[] twoSum(int[] nums, int target) {  
        for(int num1Index=0;num1Index<nums.length;num1Index++){  
            int num1 = nums[num1Index];  
  
            if(num1Index>=nums.length-1){  
                return null;  
            }  
            for(int num2Index=num1Index+1;num2Index<nums.length;num2Index++){  
                int num2 = nums[num2Index];  
  
                if(num1+num2==target){  
                    return new int[]{num1Index, num2Index};  
                }  
            }  
        }  
        return null;  
    }  
}

复杂度分析：

• 时间复杂度：O (n²)，对每个元素执行 n 次内层判断，数组长度为 n 时总操作次数为 n*(n-1)/2；
• 空间复杂度：O (1)，仅需常数级别的额外空间。

这种解法在小规模数组的场景下表现尚可，但是面对大数据量的时候，成绩就稍差了。

从执行结果来看，代码的运行时间还有很大的调整空间。既然知道了双重循环的时间复杂度是 O (n²) 了，那么我们就要先从它着手，想办法去掉双重循环，让时间复杂度减少。

第二版：哈希表解法

我们可以选择用哈希表 O (1) 的查询特性，仅单次遍历便可定位到目标元素。

例如：用一个 Map 记录下曾经访问过的数组的值，以及它的下标是多少，key 为数组中的数值，value 为它在数组中的下标。格式类似：

// 假设数组是[0, 5, 11]
{
	"0": "0",
	"5": "1",
	"11": "2"
}

这样我们就只需要循环一次数组，遍历里面的每一个值，并算出用 target 减去当前值的差值是多少。如果这个差值曾经在前面出现过，那么 Map 中就必定有它。这时候只需要将差值在 Map 中的下标值和当前值的下标返回即可。

public class TwoSum {  
    public int[] twoSum(int[] nums, int target) {  
        Map<Integer, Integer> map = new HashMap<>();  
        for(int num1Index = 0; num1Index < nums.length ; num1Index++) {  
            int num1 = nums[num1Index];  
            int num2 = target - num1;  
  
            if(map.containsKey(num2)){  
                return new int[]{num1Index, map.get(num2)};  
            }  
  
            map.put(num1, num1Index);  
        }  
        return null;  
    }  
}

复杂度分析：

• 时间复杂度：降至 O (n)，仅需一次遍历操作。
• 空间复杂度：变更为 O (n)，哈希表的最大存储量等于数组长度。

从结果来看，在运行时间上，哈希表解法比起暴力接法提升了 94%。