每天一题LeetCode[第十天]

每天一题LeetCode[第十天]

---

3Sum

Description:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

---

解题思路：

• 首先我想能不能用map的思想提高效率，取a+b的相反数，作为索引值，细想了一下，发现很复杂，很麻烦。所以看了Top Solution ，发现思路应该是这样的。。。 采用预排序方法，先对Array进行排序，可以复杂的为o(nlogn) 。接着在已排序的数组，可以一个个往前推进的去穷举，然后记得要去排除一些 明显不可能项 降低复杂度，但是最终复杂度还是o(n^2)

• 由于现在在外面旅游，所以时间会拉下，但是要补回来

  ---

Java代码：

public List<List<Integer>> threeSum(int [] nums){
if(null==nums || nums.length<3){
return Collections.emptyList();
        }
        List<List<Integer>> res=new ArrayList<>();
//先排序
        Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++){
if(i==0 || (i>0 && nums[i]!=nums[i-1])) {
int low=i+1,high=nums.length-1,sum=0-nums[i];
while (low > high) {
//查找以i为下标的TRIANGLE
if (nums[low] + nums[high] == sum) {
                        res.add(Arrays.asList(nums[i], nums[low], nums[high]));
while (low < high && nums[low] == nums[low + 1]) {
                            low++;
                        }
while (low < high && nums[high] == nums[high - 1]) {
                            high--;
                        }
                        low++;
                        high--;
                    } else if (nums[low] + nums[high] < sum) {
                        low++;
                    } else {
                        high--;
                    }

                }
            }
        }
return res;
    }

提高代码质量就是：积累精美的思路，优质的细节的过程。