15. 三数之和

发表评论
514 views

 ›
15. 三数之和

官方地址

https://leetcode-cn.com/problems/3sum/

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

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

解法一 暴力求解

三重循环 O(n^3)

解法二 hash 表

记录 a, b, a + b = -c O(n^2)

解法三 左右下标推进

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3: return []

        nums.sort()
        res = set()

        for i, v in enumerate(nums[:-2]):
            if i >= 1 and v == nums[i-1]:
                continue
            d = {}
            for x in nums[i+1:]:
                if x not in d:
                    d[-v-x] = 1
                else:
                    res.add((v, -v-x, x))

        return list(map(list, res)) # python2: map(list, res)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()

        res = []
        for k in range(len(nums)-2):
            if nums[k] > 0: break # 大于零，说明和一定大于零
            if k > 0 and nums[k-1] == nums[k]: continue # 跳过重复的元素
            i, j = k+1, len(nums)-1  
            while i<j:
                s = nums[k] + nums[i] + nums[j]
                if s < 0:
                    i += 1
                    while i<j and nums[i] == nums[i-1]: i += 1
                if s > 0:
                    j -= 1
                    while i<j and nums[j] == nums[j+1]: j -= 1
                if s == 0:
                    res.append([nums[k],nums[i],nums[j]])
                    i += 1
                    j -= 1
                    while i<j and nums[i] == nums[i-1]: i += 1
                    while i<j and nums[j] == nums[j+1]: j -= 1
        return res

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {

            if(nums[i] > 0) break; 
            if(i > 0 && nums[i] == nums[i-1]) continue;

            int j = i + 1;
            int k = nums.length - 1;

            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum > 0) {
                    k--;
                    while (j < k && nums[k] == nums[k+1]) k--; 
                } else if (sum < 0) {
                    j++;
                    while (j < k && nums[j] == nums[j-1]) j++;
                } else {
                    List<Integer> list = new ArrayList<>();

                    Integer [] values = {nums[i], nums[j], nums[k]};
                    Collections.addAll(list, values);

                    // list.add(nums[k]);
                    // list.add(nums[i]);
                    // list.add(nums[j]);

                    result.add(list);

                    j++;
                    k--;
                    while (j < k && nums[j] == nums[j-1]) j++;
                    while (j < k && nums[k] == nums[k+1]) k--; 
                }
            }
        }
        return result;
    }
}