Leetcode 15 3Sum

Datetime:2016-08-23 01:20:21          Topic: LeetCode           Share

Given an array S of  n integers, are there elements  abc in  S such that  abc = 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]
]

Solution:

此题的关键在于如何避免duplicate triplets. 此处解决方法为只考虑首次出现的值,以[-4,-1,-1,-1,0,1,2]为例,循环第一次到-1时,所有跟-1有关的triplets [-1,0,1],[-1,-1,2]已经出现,则第二次循环到-1的时候,忽略这个subloop一直到发现下一个非-1的值,
此处为0.
public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        List<int> newList = nums.ToList();
            List<IList<int>> returnList = new List<IList<int>>();
            newList.Sort();
            for(int i = 0; i < newList.Count() -2; i++)
            {
                if((i == 0)||( (newList[i] != newList[i - 1])))
                {
                    int low = i + 1;
                    int high = nums.Length - 1;
                    int sum = 0 - newList[i];
                    while(low < high)
                    {
                        if(newList[low]+newList[high] == sum)
                        {
                            returnList.Add(new List<int>() { newList[i?], newList[low], newList[high] });
                            while ((low < high) && (newList[low] == newList[low + 1])) low++;//duplicate
                            while ((low < high) && (newList[high] == newList[high - 1])) high--;//duplicate
                            low++;
                            high--;
                        }
                        else if(newList[low]+newList[high] < sum)
                        {
                            low++;
                        }
                        else
                        {
                            high--;
                        }
                    }
                }
            }
            return returnList;
        
    }
}




About List