LeetCode.jpg

三數(shù)之和

給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，

滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]

Python3實(shí)現(xiàn)

借助兩數(shù)之和

# @author:leacoder
# @des:   借助兩數(shù)之和  三數(shù)之和

class Solution(object):
    def threeSum(self, nums):
        nums.sort() #排序 方便去重
        res = []
        for i, num in enumerate(nums): #一層循環(huán)
            if i > 0 and nums[i] == nums[i-1]: # 避免重復(fù)
                continue
                
            new_nums = nums[i+1:] #剔除 一層循環(huán)后的數(shù) 
            two_sums = self.twoSum(new_nums, -num) #由于何為0  兩數(shù)之和要為 -num
            for two_sum in two_sums:
                res.append([num, new_nums[two_sum[0]], new_nums[two_sum[1]]])
                         
        return res
            
        
    def twoSum(self, nums, target):
        d = {}
        res = []
        hit = False
        for i, num in enumerate(nums):
            if i > 1 and nums[i] == nums[i-1] and hit:
                continue
            if num in d:
                res.append([d[num], i])
                hit = True
            else:
                d[target - num] = i
                hit = False
        return res

一層枚舉 左右兩指針形式

# @author:leacoder
# @des:   一層枚舉 左右兩指針形式  三數(shù)之和 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for index1,value in enumerate(nums[:-2]): #一層循環(huán)
            if index1>0 and nums[index1] == nums[index1-1]: #不可以包含重復(fù)的三元組
                continue
            left,right = index1+1,len(nums)-1  #左右指針形式  左：一層數(shù)據(jù)右側(cè)開(kāi)始  右:數(shù)據(jù)最右端開(kāi)始
            while left<right: #循環(huán)條件  依據(jù)實(shí)際大小情況，選擇左或右指針向中間移動(dòng)  但右必定大于左
                sumtmp = nums[index1] + nums[left] + nums[right] #三數(shù)和
                if sumtmp <0: left +=1 # <0 表明和小了，那么左指針向右+1 真大 nums[left]  nums已經(jīng)排序 右邊必定大于 左邊
                elif sumtmp >0: right -=1 #同上 
                else: #剛好為0
                    res.append((nums[index1],nums[left],nums[right]))
                    while left < right and nums[left]==nums[left+1]: #不可以包含重復(fù)的三元組
                        left +=1
                    while left < right and nums[right]==nums[right-1]:#不可以包含重復(fù)的三元組
                        right -=1
                    left +=1;right -=1
        return res
                

C++實(shí)現(xiàn)

一層枚舉 左右兩指針形式

/*
 *@author:leacoder
 *@des:   一層枚舉 左右兩指針形式  三數(shù)之和 
 */
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res; //返回值
        if(nums.size()<3){ //輸入檢查
            return res;
        }
        sort(nums.begin(), nums.end()); //排序
        
        for (int i = 0; i < nums.size()-2; i++) //一層循環(huán)
        {
            if(i>0 && nums[i] == nums[i-1])
                continue;
            int target = -nums[i]; //其他兩數(shù)和
            int l = i + 1, r = nums.size() - 1; //左右指針形式  l 左 r右
            while (l < r)
            {
                if (nums[l] + nums[r] < target) //小于目標(biāo) l 增加
                    ++l;
                else if (nums[l] + nums[r] > target) //大于目標(biāo) r 減少
                    --r;
                else{ //剛好
                    res.push_back(vector<int>{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--;
                }
            }
            
        }
        return res;
    }
};

GitHub鏈接：
https://github.com/lichangke/LeetCode
知乎個(gè)人首頁(yè)：
https://www.zhihu.com/people/lichangke/
個(gè)人Blog:
https://lichangke.github.io/
歡迎大家來(lái)一起交流學(xué)習(xí)