leetcode——15.三数之和

我自己写的超时了。。。。

class Solution:
    def threeSum(self, nums) :
        nums.sort()
        #print(nums)
        nums1=[]
        s=[]
        if nums.count(0)>=3:
            s.append([0,0,0])
        for i in range(len(nums)-2):
            #print('i= '+str(i))
            for j in range(i+1,len(nums)-1):
                #print('j= '+str(j))
                if 0-(nums[i]+nums[j]) in nums[j+1:]:
                    if [nums[i],nums[j],0-(nums[i]+nums[j])] not in s:
                        s.append([nums[i],nums[j],0-(nums[i]+nums[j])])
        return s

看了别人的代码，说是使用排序+双指针。

以下是我的修改：

class Solution:
    def threeSum(self, nums) :
        nums.sort()
        #print(nums)
        nums1=[]
        nums2=[]
        s=[]
        if nums.count(0)>=3:
            s.append([0,0,0])
        for i in range(len(nums)-1,-1,-1):
            if nums[i]>0:
                nums1.append(nums[i])
            else:
                nums2.append(nums[i])
        #print(nums1)#存放正数
        #print(nums2)#存放非正数
        
        
        for i in range(len(nums)-1):
            if i>0:
                if nums[i]==nums[i-1]:
                    continue#如果是相同的数，则跳过
            left,right=i+1,len(nums)-1#两个指针
            #print('i= '+str(i))
            while left<right: #左指针小于右指针
                sums=nums[i]+nums[left]+nums[right]
                #print('sums= '+str(sums))
                if right<len(nums2):
                    break
                if sums==0:
                    s.append([nums[left],nums[i],nums[right]])
                    while left<right and nums[left]==nums[left+1]:
                        left+=1
                    while left<right and nums[right]==nums[right-1]:
                        right-=1
                    left+=1
                    right-=1
                elif sums<0:
                    left+=1
                elif sums>0:
                    right-=1
        return s

执行用时 :1112 ms, 在所有 Python3 提交中击败了70.10%的用户

内存消耗 :16.9 MB, 在所有 Python3 提交中击败了29.41%的用户

 

                                                                                                   ——2019.10.7

 

---

public List<List<Integer>> threeSum(int[] nums) {//三数之和，
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);  //先进行排序
        int len = nums.length;
        for(int i = 0;i<len-2;i++){
            if(i>0 && nums[i] == nums[i-1]){
                continue;
            }
            int k = len - 1;
            for(int j = i+1;j<len;j++){
                if(j>i + 1 && nums[j] == nums[j-1]){
                    continue;
                }
                while(k>j && nums[j] + nums[k] > -nums[i]){
                    k--;
                }
                if(k == j){
                    break;
                }
                if(nums[i] + nums[j] + nums[k] == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    lists.add(list);
                }
            }
        }
        return lists;
    }

 双指针，对j也进行了遍历，这一点我没考虑到。

——2020.7.9