leetcode15

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);

        List<List<Integer>> ls = new LinkedList<>();

        for (int i = 0; i < nums.length - 2; i++) {

            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {  // 跳过可能重复的答案

                int l = i + 1, r = nums.length - 1, sum = 0 - nums[i];

                while (l < r) {

                    if (nums[l] + nums[r] == sum) {

                        ls.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 (nums[l] + nums[r] < sum) {

                        while (l < r && nums[l] == nums[l + 1]) l++;   // 跳过重复值

                        l++;

                    } else {

                        while (l < r && nums[r] == nums[r - 1]) r--;

                        r--;

                    }

                }

            }

        }

        return ls;

    }

}

使用python实现：

 class Solution:

     def threeSum(self, nums: 'List[int]') -> 'List[List[int]]':

         nums = sorted(nums)

         res = []

         n = len(nums)

         for i in range(n-2):

             if i == 0 or nums[i] != nums[i-1]:

                 l,r,sums = i + 1,n-1,0-nums[i]

                 while l < r:

                     if nums[l] + nums[r] == sums:

                         res.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] < sums:

                         while l < r and nums[l] == nums[l+1]:

                             l += 1

                         l += 1

                     else:

                         while l < r and nums[r] == nums[r-1]:

                             r -= 1

                         r -= 1

         return res

下面补充另一种思路，使用python实现，是根据leetcode167 twonum II的思路来做的，效率比上面的方法要高一些，代码如下：

 class Solution:

     def towSum(self,numbers,target):

         i = 0

         j = len(numbers) - 1

         ary = list()

         while i < j:

             sums = numbers[i] + numbers[j]

             #print(str(i)+','+str(j)+'->'+str(sums))

             if sums == target:

                 #return numbers[i],numbers[j]

                 ary.append([numbers[i],numbers[j]])

                 while i < j and numbers[i]==numbers[i+1]:

                     i+=1

                 i+=1

             elif sums < target:

                 i+=1

             else:

                 j-=1

         return ary

     def threeSum(self, nums: 'List[int]') -> 'List[List[int]]':

         result = list()

         sortedlist = sorted(nums)

         zlist = list(filter(lambda x:x==0,sortedlist))

         if len(zlist) >= 3:

             result.append([0,0,0])

         nlist = list(filter(lambda x:x<0,sortedlist))

         nset = set(nlist)

         plist = list(filter(lambda x:x>=0,sortedlist))

         pset = set(plist)

         for target in nset:

             aa = self.towSum(plist,target*-1)

             for a in aa:

                 a1 = a[0]

                 a2 = a[1]

                 clist = [a1,a2,target]

                 result.append(clist)

         for target in pset:

             aa = self.towSum(nlist,target*-1)

             for a in aa:

                 a1 = a[0]

                 a2 = a[1]

                 clist = [a1,a2,target]

                 result.append(clist)

         return result