数组：求和

0001. 两数之和 (opens new window)

题目

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

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

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

示例 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.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• 只会存在一个有效答案

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

解析

使用 Hash 表记录所有已遍历元素及对应的下标，遍历的同时查找满足条件的数字是否已遍历，若找到返回即可。

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {        
        unordered_map<int, int> record;
        for (int i = 0; i < nums.size(); i++) {
            int num = target - nums[i];
            if (record.find(num) != record.end()) {
                return vector<int>{record[num], i};
            }
            record[nums[i]] = i;
        }
        return vector<int>{-1, -1};
    }
};

func twoSum(a []int, trg int) (ans []int) {
    h := map[int]int{}
    for i, x := range a {
        if p, ok := h[trg-x]; ok {
            return []int{p, i}
        }
        h[x] = i
    }
    return nil
}

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = {}
        for i, num in enumerate(nums):
            x = target - num
            if x in record:
                return [record[x], i]
            record[num] = i
        return [-1, -1]

0015. 三数之和 (opens new window)

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

解析

由于需要求三个数字的和，遍历复杂度不会小于 $O(n^2)$，因此可以先对数组排序，这样方便之后处理。

整体思路为，通过遍历数组选取第一个数字，在遍历的同时用前后双指针寻找满足条件的数字即可。

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = nums.size() - 1;
            int target = 0 - nums[i];
            while (l < r) {
                if (nums[l] + nums[r] == target) {
                    ans.push_back({nums[i], nums[l], nums[r]});
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++, r--;
                } else if (nums[l] + nums[r] < target) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return ans;
    }
};

func threeSum(nums []int) (ans [][]int) {
    sort.Ints(nums)
    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        l, r := i+1, len(nums)-1
        target := 0 - nums[i]
        for l < r {
            if nums[l]+nums[r] == target {
                ans = append(ans, []int{nums[i], nums[l], nums[r]})
                for l < r && nums[l] == nums[l+1] {
                    l++
                }
                for l < r && nums[r] == nums[r-1] {
                    r--
                }
                l++
                r--
            } else if nums[l]+nums[r] < target {
                l++
            } else {
                r--
            }
        }
    }
    return
}

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort()
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            l, r = i + 1, len(nums) - 1
            target = 0 - nums[i]
            while l < r:
                if nums[l] + nums[r] == target:
                    ans.append([nums[i], nums[l], nums[r]])
                    while l < r and nums[l] == nums[l + 1]:
                        l += 1
                    while l < r and nums[r] == nums[r - 1]:
                        r -= 1
                    l += 1
                    r -= 1
                elif nums[l] + nums[r] < target:
                    l += 1
                else:
                    r -= 1
        return ans

0016. 最接近的三数之和 (opens new window)

题目

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

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

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -10^4 <= target <= 10^4

解析

本题思路与 0015. 三数之和 类似，只是更新结果的条件变为比较差值的大小，保留差值更小的结果。

代码

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int ans = nums[0] + nums[1] + nums[2];
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == target) return sum;
                if (abs(sum - target) < abs(ans - target)) ans = sum;
                if (sum < target) l++;
                else r--;
            }
        }
        return ans;
    }
};

func threeSumClosest(nums []int, target int) int {
    ans := nums[0] + nums[1] + nums[2]
    sort.Ints(nums)
    for i := 0; i < len(nums); i++ {
        l, r := i+1, len(nums)-1
        for l < r {
            sum := nums[i] + nums[l] + nums[r]
            if sum == target {
                return sum
            }
            if abs(sum-target) < abs(ans-target) {
                ans = sum
            }
            if sum < target {
                l++
            } else {
                r--
            }
        }
    }
    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        ans = nums[0] + nums[1] + nums[2]
        nums.sort()
        for i in range(len(nums)):
            l, r = i + 1, len(nums) - 1
            while l < r:
                _sum = nums[i] + nums[l] + nums[r]
                if _sum == target:
                    return _sum
                if abs(_sum - target) < abs(ans - target):
                    ans = _sum
                if _sum < target:
                    l += 1
                else:
                    r -= 1
        return ans

0018. 四数之和 (opens new window)

题目

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

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

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

解析

本题思路与 0015. 三数之和 相同，只需增加一层循环，枚举前两个数字的值，双指针确定后两个数字的值即可。

代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < nums.size(); j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int l = j + 1, r = nums.size() - 1;
                long long sum = (long long)target - nums[i] - nums[j];
                while (l < r) {
                    if (nums[l] + nums[r] == sum) {
                        ans.push_back({nums[i], nums[j], nums[l], nums[r]});
                        while (l < r && nums[l] == nums[l + 1]) l++;
                        while (l < r && nums[r] == nums[r - 1]) r--;
                        l++, r--;
                    } else if (nums[l] + nums[r] < sum) {
                        l++;
                    } else {
                        r--;
                    }
                }
            }
        }
        return ans;
    }
};

func fourSum(nums []int, target int) (ans [][]int) {
    sort.Ints(nums)
    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for j := i + 1; j < len(nums); j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            l, r := j+1, len(nums)-1
            sum := target - nums[i] - nums[j]
            for l < r {
                if nums[l]+nums[r] == sum {
                    ans = append(ans, []int{nums[i], nums[j], nums[l], nums[r]})
                    for l < r && nums[l] == nums[l+1] {
                        l++
                    }
                    for l < r && nums[r] == nums[r-1] {
                        r--
                    }
                    l++
                    r--
                } else if nums[l]+nums[r] < sum {
                    l++
                } else {
                    r--
                }
            }
        }
    }
    return
}

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        ans = []
        nums.sort()
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, len(nums)):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                l, r = j + 1, len(nums) - 1
                _sum = target - nums[i] - nums[j]
                while l < r:
                    if nums[l] + nums[r] == _sum:
                        ans.append([nums[i], nums[j], nums[l], nums[r]])
                        while l < r and nums[l] == nums[l + 1]:
                            l += 1
                        while l < r and nums[r] == nums[r - 1]:
                            r -= 1
                        l += 1
                        r -= 1
                    elif nums[l] + nums[r] < _sum:
                        l += 1
                    else:
                        r -= 1
        return ans

0167. 两数之和 II - 输入有序数组 (opens new window)

题目

给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

解析

由于数组有序，因此使用前后双指针移动寻找目标值即可。

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        while (low < high) {
            int sum = nums[low] + nums[high];
            if (sum == target) {
                return vector<int>{low + 1, high + 1};
            } else if (sum < target) {
                low ++;
            } else {
                high --;
            }
        }
        return vector<int>{-1, -1};
    }
};

0259. 较小的三数之和 (opens new window)

题目

给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组  i, j, k 个数（0 <= i < j < k < n）。

解析

首先对数组排序，之后遍历枚举第一个数字，前后双指针寻找满足条件的后两个数字。

这里用到一个技巧，即：ans += high - low，由于 high 的位置满足条件，因此 low 和 high 之间的所有数字均满足条件，直接累加即可。

代码

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        int ans = 0;
        if (nums.size() < 3) {
            return ans;
        }
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 2; i ++) {
            int low = i + 1;
            int high = nums.size() - 1;
            while (low < high) {
                if (nums[i] + nums[low] + nums[high] < target) {
                    ans += high - low;
                    low ++;
                } else {
                    high --;
                }
            }
        }
        return ans;
    }
};

0454. 四数相加 II (opens new window)

题目

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 $-2^{28}$ 到 $2^{28}$ - 1 之间，最终结果不会超过 $2^{31}$ - 1 。

解析

将四个数组分为两部分处理，使用一个 Hash 表记录 A、B 的和出现的次数，之后遍历 C、D，寻找满足条件的和的次数相加即可。

代码

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> record;
        for (int i = 0; i < A.size(); i ++) {
            for (int j = 0; j < B.size(); j ++) {
                record[A[i] + B[j]] ++;
            }
        }
        int ans = 0;
        for (int i = 0; i < C.size(); i ++) {
            for (int j = 0; j < D.size(); j ++) {
                int sum = - C[i] - D[j];
                if (record.find(sum) != record.end()) {
                    ans += record[sum];
                }
            }
        }
        return ans;
    }
};