LeetCode-CSharp/Solution/0015.3Sum/0015-3Sum.cs at main · FakeStandard/LeetCode-CSharp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Solution._0015._3Sum
{
    public class _0015_3Sum
    {
        public IList<IList<int>> ThreeSum(int[] nums)
        {
            var res = new List<IList<int>>();

            if (nums == null || nums.Length == 0) return res;

            Dictionary<int, int> dic = new Dictionary<int, int>();

            foreach (int num in nums)
            {
                if (dic.ContainsKey(num)) dic[num]++;
                else dic.Add(num, 1);
            }

            int diff = 0;
            Array.Sort(nums);

            for (int i = 0; i < nums.Length - 2; i++)
            {
                if (i > 0 && nums[i] == nums[i - 1]) continue;

                for (int j = i + 1; j < nums.Length - 1; j++)
                {
                    if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                    diff = 0 - nums[i] - nums[j];

                    if (diff > nums[j] && dic.ContainsKey(diff)) res.Add(new int[] { nums[i], nums[j], diff });
                    else if (diff == nums[j] && diff == nums[j + 1]) res.Add(new int[] { nums[i], diff, diff });
                }
            }

            return res;
        }

        // Time Limit Exceeded
        //public IList<IList<int>> ThreeSum(int[] nums)
        //{
        //    IList<IList<int>> res = new List<IList<int>>();

        //    if (nums.Length < 3) return res;

        //    // bubble sort
        //    int tmp = 0;
        //    int flag = 0;

        //    for (int i = nums.Length - 1; i > 0; i--)
        //    {
        //        flag = 0;

        //        for (int j = 0; j < i; j++)
        //        {
        //            if (nums[j] > nums[j + 1])
        //            {
        //                // swap
        //                tmp = nums[j];
        //                nums[j] = nums[j + 1];
        //                nums[j + 1] = tmp;

        //                flag++;
        //            }
        //        }

        //        if (flag == 0) break;
        //    }

        //    //
        //    for (int i = 0; i < nums.Length; i++)
        //    {
        //        for (int j = i + 1; j < nums.Length; j++)
        //        {
        //            for (int k = j + 1; k < nums.Length; k++)
        //            {
        //                if (nums[i] + nums[j] + nums[k] == 0)
        //                {
        //                    List<int> list = new List<int>();
        //                    list.Add(nums[i]);
        //                    list.Add(nums[j]);
        //                    list.Add(nums[k]);

        //                    if (Traverse(res, list))
        //                        res.Add(list);
        //                }
        //            }
        //        }
        //    }

        //    return res;
        //}

        //private bool Traverse(IList<IList<int>> res, List<int> list)
        //{
        //    for (int i = 0; i < res.Count; i++)
        //    {
        //        //if (res[i][0] == list[0] && res[i][1] == list[1] && res[i][2] == list[2]) return false;

        //        // linq
        //        if (Enumerable.SequenceEqual(res[i], list)) return false;
        //    }

        //    return true;
        //}
    }
}