JAVA 牛牛

15. 三数之和

  • May 19, 2020
  • 0 views
  • 难度：中等
  • 本题涉及算法： 数组遍历
  • 思路： 数组遍历
  • 类似题型:

题目 15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

方法一 数组遍历

  • 解题思路：
    • 首先对数组进行排序，排序后固定一个数 $nums[i]$，再使用左右指针指向 $nums[i]$ 后面的两端，数字分别为 $nums[L]$ 和 $nums[R]$，计算三个数的和 $sum$ 判断是否满足为 $0$，满足则添加进结果集
    • 如果 $nums[i]$ 大于 $0$，则三数之和必然无法等于 $0$，结束循环
    • 如果 $nums[i]= nums[i−1]$，则说明该数字重复，会导致结果重复，所以应该跳过
    • 当 $sum0 时，$nums[L] = nums[L+1]$ 则会导致结果重复，应该跳过，$L++$
    • 当 $sum0$ 时，$nums[R] =nums[R−1]$ 则会导致结果重复，应该跳过，$R–$
  • 时间复杂度：
    • 时间复杂度：$O(n^2)$ $n$ 为数组长度
    • 空间复杂度：$O(1)$

java

class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return ans;
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int L = i+1;
            int R = len-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(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 (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }        
        return ans;
    }
}

python

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums_len = len(nums)
        ans = []
        if not nums or nums_len < 3: return ans
        nums.sort()
        for i in range(nums_len):
            if nums[i] > 0: return ans
            if i > 0 and nums[i] == nums[i-1]: continue
            left = i + 1
            right = nums_len - 1
            while left < right:
                if nums[left] + nums[right] + nums[i] == 0:
                    ans.append([nums[i] ,nums[left] ,nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left = left + 1
                    while left < right and nums[right] == nums[right - 1]:
                        right = right - 1
                    left = left + 1
                    right = right - 1
                elif nums[left] + nums[right] + nums[i] > 0:
                    right = right - 1
                else:
                    left = left + 1
        return ans
Search