【算法题解】20. 两数之和

野性酷女 2024-03-26 21:30 35阅读 0赞

> 这是一道 **简单** 题
> 
> 题目来自： [https://leetcode.cn/problems/two-sum/][https_leetcode.cn_problems_two-sum]

### 题目 ###

给定一个整数数组 `nums` 和一个整数目标值 `target`，请你在该数组中找出 **和为目标值** `target` 的那 **两个** 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

**提示：**

*   2 < = n u m s . l e n g t h < = 1 0 4 2 <= nums.length <= 10^4 2<=nums.length<=104
 *   − 1 0 9 < = n u m s \[ i \] < = 1 0 9 -10^9<= nums\[i\] <= 10^9 −109<=nums\[i\]<=109
 *   − 1 0 9 < = t a r g e t < = 1 0 9 -10^9 <= target <= 10^9 −109<=target<=109
 *  **只会存在一个有效答案**

**进阶：** 你可以想出一个时间复杂度小于  O ( n 2 ) O(n^2) O(n2) 的算法吗？

**示例 1：**

输入：nums = [2,7,11,15], target = 9 
    输出：[0,1] 
    解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

--------------------

**示例 2：**

输入：nums = [3,2,4], target = 6 
    输出：[1,2]

--------------------

**示例 3：**

输入：nums = [3,3], target = 6 
    输出：[0,1]

### 暴力解法 ###

#### 思路 ####

最简单的算法思路，`2` 层循环，当遇到两个数 `nums[i]`和 `nums[j]` 的和为 `target` 的时候，返回对应的下标 `i, j`。

#### Java 代码实现 ####

class Solution {
        
        public int[] twoSum(int[] nums, int target) {
        
            int n = nums.length;
            for(int i = 0; i < n; i++){
        
                for(int j = i + 1; j < n; j++){
        
                    if(nums[i] + nums[j] == target){
        
                        return new int[]{
        i, j};
                    }
                }
            }
    
            return null;
        }
    }

#### Go 代码实现 ####

func twoSum(nums []int, target int) []int {
        
    
        n := len(nums)
        for i := 0; i < n; i++ {
        
            for j := i + 1; j < n; j++ {
        
                if nums[i] + nums[j] == target {
        
                    return []int{
        i, j}
                }
            }
        }
        return nil
    }

#### 复杂度分析 ####

时间复杂度为 O ( N 2 ) O(N^2) O(N2)，空间复杂度为 O ( 1 ) O(1) O(1)。

### 哈希表 ###

#### 思路 ####

创建一个哈希表map，`key` 为数字本身，`value` 为下标。

遍历数组中的每一个元素 `nums[i]`, 并寻找与之对应的另一个数字 `target - nums[i]`：

1.  当 `map` 中包含 `Integer r = target - nums[i]` 时，说明已找到答案，返回 `r 的下标` 和当前下标 `i`。
2.  当 `map` 中不包含 `Integer r = target - nums[i]` 时，将数字 `nums[i]` 和其下标 `i` 放入 `map`。

![【算法题解】20. 两数之和][20.]

#### Java 代码实现 ####

class Solution {
        
        private Map<Integer, Integer> map = new HashMap<>();
        public int[] twoSum(int[] nums, int target) {
        
            int n = nums.length;
            for(int i = 0; i < n; i++){
        
                Integer r = target - nums[i];
                if(map.containsKey(r)){
        
                    return new int[]{
        map.get(r), i};
                }else{
        
                    map.put(nums[i], i);
                }
            }
            return null;
        }
    }

#### Go 代码实现 ####

func twoSum(nums []int, target int) []int {
        
    
        hashMap := map[int]int{
        }
        
        for i, v := range nums {
        
            r := target - v
            if j, ok := hashMap[r]; ok {
        
                return []int{
        j, i}
            }
            hashMap[v] = i
        }
        return nil
    }

#### 复杂度分析 ####

时间复杂度为  O ( N ) O(N) O(N)。

空间复杂度为  O ( N ) O(N) O(N)。

### 双指针 ###

#### 思路 ####

**双指针算法要求必须是排好序的数组**，所以首先应当将原数组排序。又因为结果要求返回的是下标，所以排序后仍然需要保留原数组的下标。

分别创建两个指针 left 和 right，然后让 left 指针指向第 0 个数字，也就是最小的数字；让 right 指针指向第 n - 1 个数字，也就是最大的数字。

1.  当 nums\[left\] + nums\[right\] == target 时：返回nums\[left\] 和 nums\[right\] 在原数组中的下标。
2.  当 nums\[left\] + nums\[right\] > target 时: 需要将 nums\[left\] + nums\[right\] 的值减小才能匹配到结果，所以需要将 right 指针向前移动一步。
3.  当 nums\[left\] + nums\[right\] < target 时: 需要将 nums\[left\] + nums\[right\] 的值增大才能匹配到结果，所以需要将 left 指针向后移动一步。

![【算法题解】20. 两数之和][20. 1]

#### Java 代码实现 ####

class Solution {
        
        public int[] twoSum(int[] nums, int target) {
        
            int n = nums.length;
            // 二维数组，
            // numAndIndex[i][0]存放数字本身
            // numAndIndex[i][1]存放数字原始位置
            int[][] numAndIndex = new int[n][2];
            for(int i = 0; i < n; i++){
        
                numAndIndex[i][0] = nums[i];
                numAndIndex[i][1] = i;
            }
    
            Arrays.sort(numAndIndex, (ni1, ni2) -> {
        
                return ni1[0] == ni2[0] ? ni1[1] - ni2[1] : ni1[0] - ni2[0];
            });
    
            int left = 0, right = n - 1;
            while(left < right){
        
                if(numAndIndex[left][0] + numAndIndex[right][0] == target){
        
                    return new int[]{
        numAndIndex[left][1], numAndIndex[right][1]};
                }else if(numAndIndex[left][0] + numAndIndex[right][0] > target){
        
                    right--;
                }else{
        
                    left++;
                }
            }
    
            return null;
    
        }
    }

#### Go 代码实现 ####

func twoSum(nums []int, target int) []int {
        
    
        n := len(nums)
        var numAndIndex [][2]int
        for i, v := range nums {
        
            numAndIndex = append(numAndIndex, [2]int{
        v, i})
        }
    
        sort.Slice(numAndIndex, func(i, j int) bool {
        
            if numAndIndex[i][0] == numAndIndex[j][0] {
        
                return numAndIndex[i][1] < numAndIndex[j][1]
            }else {
        
                return numAndIndex[i][0] < numAndIndex[j][0]  
            }
        })
       
        left, right := 0, n - 1
        for left < right {
        
            if numAndIndex[left][0] + numAndIndex[right][0] == target {
        
                return []int{
        numAndIndex[left][1], numAndIndex[right][1]}
            }else if numAndIndex[left][0] + numAndIndex[right][0] > target {
        
                right--
            }else{
        
                left++
            }
        }
        return nil
    }

#### 复杂度分析 ####

时间复杂度为  O ( N ) O(N) O(N)，第一个`for`循环共执行`N`次，第二个`while`循环最多执行`N`次。

空间复杂度为  O ( N ) O(N) O(N)，数组 `numAndIndex` 长度为`N`。

[https_leetcode.cn_problems_two-sum]: https://leetcode.cn/problems/two-sum/
[20.]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/941407c0e631446aaa2e0951d9f3c049.png
[20. 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/08ab36ab17ed4dd59dcc5aaa121e1a48.png