[LeetCode] 15. 3Sum

 

 

 

https://leetcode.com/problems/3sum/description/

 

public IList<IList<int>> ThreeSum(int[] nums)
{
    var plusDict = new Dictionary<int, int>();
    var minusDict = new Dictionary<int, int>();

    int zeroCount = 0;

    foreach (int num in nums)
    {
        if (num == 0)
        {
            ++zeroCount;
        }

        if (num >= 0)
        {
            if (plusDict.ContainsKey(num) == false)
                plusDict[num] = 0;

            ++plusDict[num];
        }
        else
        {
            if (minusDict.ContainsKey(num) == false)
                minusDict[num] = 0;

            ++minusDict[num];
        }
    }

    var answer = new List<IList<int>>();

    if (zeroCount >= 3)
    {
        answer.Add(new List<int> { 0, 0, 0 });
    }

    var plusList = plusDict.Keys.ToList();
    for (int i = 0; i < plusList.Count; i++)
    {
        int fixPlusNum = plusList[i];

        for (int j = i; j < plusList.Count; j++)
        {
            int plusNum = plusList[j];
            int count = plusDict[plusNum];

            if (fixPlusNum == plusNum && count < 2)
                continue;

            if (minusDict.ContainsKey(-(fixPlusNum + plusNum)))
            {
                answer.Add(new List<int> { fixPlusNum, plusNum, -(fixPlusNum + plusNum) });
            }
        }
    }

    var minusList = minusDict.Keys.ToList();
    for (int i = 0; i < minusList.Count; i++)
    {
        int fixMinusNum = minusList[i];

        for (int j = i; j < minusList.Count; j++)
        {
            int minusNum = minusList[j];
            int count = minusDict[minusNum];

            if (fixMinusNum == minusNum && count < 2)
                continue;

            if (plusDict.ContainsKey(-(fixMinusNum + minusNum)))
            {
                answer.Add(new List<int> { fixMinusNum, minusNum, -(fixMinusNum + minusNum) });
            }
        }
    }

    return answer;
}

 

public IList<IList<int>> ThreeSum(int[] nums)
{
    var answer = new List<IList<int>>();

    Array.Sort(nums);

    int start = 0;

    while (start < nums.Length - 2)
    {
        int left = start + 1;
        int right = nums.Length - 1;

        while (left < right)
        {
            if (nums[start] + nums[left] + nums[right] == 0)
            {
                var oneSolution = new List<int>() { nums[start], nums[left], nums[right] };
                answer.Add(oneSolution);

                while ((left < right) && (nums[left] == oneSolution[1]))
                    ++left;

                while ((left < right) && (nums[right] == oneSolution[2]))
                    --right;
            }
            else if (nums[left] + nums[right] < -nums[start])
            {
                ++left;
            }
            else
            {
                --right;
            }
        }

        int startNum = nums[start];
        while ((start < nums.Length - 2) && (nums[start] == startNum))
            ++start;
    }

    return answer;
}