LeetCodeCSharp/Solutions/Problems/TwoSum.cs at main · gabaoalb/LeetCodeCSharp · 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
namespace Solutions.Problems;

public class TwoSumSolution
{
    /// <summary>
    /// Brute Force
    /// </summary>
    /// <param name="nums"></param>
    /// <param name="target"></param>
    /// <returns></returns>
    public int[] TwoSumBruteForce(int[] nums, int target)
    {
        for (int x = 0; x < nums.Length; x++)
            for (int y = x + 1; y < nums.Length; y++)
                if (nums[x] + nums[y] == target)
                    return [x, y];

        return [];
    }

    /// <summary>
    /// Sorting two pointers
    /// </summary>
    /// <param name="nums"></param>
    /// <param name="target"></param>
    /// <returns></returns>
    public int[] TwoSumSorting(int[] nums, int target)
    {
        var sorted = nums.Select((num, index) => (num, index)).OrderBy(x => x.num).ToArray();
        (int left, int right) = (0, sorted.Length - 1);

        while (left < right)
        {
            int sum = sorted[left].num + sorted[right].num;
            if (sum == target)
                return [sorted[left].index, sorted[right].index];
            else if (sum < target)
                left++;
            else
                right--;
        }

        return [];
    }

    /// <summary>
    /// HashMap two pass
    /// </summary>
    /// <param name="nums"></param>
    /// <param name="target"></param>
    /// <returns></returns>
    public int[] TwoSumHashMapTwoPass(int[] nums, int target)
    {
        Dictionary<int, int> hashMap = [];

        // hashMap = nums.Select((value, index) => (value, index)).ToDictionary(x => x.value, x => x.index);
        for (int index = 0; index < nums.Length; index++)
            hashMap[nums[index]] = index;

        for (int index = 0; index < nums.Length; index++)
        {
            int diff = target - nums[index];
            if (hashMap.TryGetValue(diff, out int value) && value != index)
                return [index, value];
        }

        return [];
    }

    /// <summary>
    /// HashMap one pass
    /// </summary>
    /// <param name="nums"></param>
    /// <param name="target"></param>
    /// <returns></returns>
    public int[] TwoSum(int[] nums, int target)
    {
        Dictionary<int, int> hashMap = [];

        for (int index = 0; index < nums.Length; index++)
        {
            int diff = target - nums[index];
            if (hashMap.TryGetValue(diff, out int value))
                return [value, index];
            hashMap[nums[index]] = index;
        }

        return [];
    }
}