CC's Boat

一顾青山舟远去，归来仍是顾青山

0%

代码随想录算法训练营第七天｜454-383-15-18

Posted on

LeetCode 454.四数相加-ii

这道题的如果直接使用循环的话其时间复杂度是O(n^4)，所以考虑拆成两部分并使用hashmap cache住一部分的结果，可以把时间复杂度降低到O(n^2)

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
class Solution {
    // public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {

    //     int ans = 0;
		// a simple way is use 4-level embedded looping, but would result in runtime exceed
    //     for (int i = 0; i < nums1.length; i++) {
    //         for (int j = 0; j < nums2.length; j++) {
    //             for (int k = 0; k < nums3.length; k++) {
    //                 for (int l = 0; l < nums4.length; l++) {
    //                     if(nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) {
    //                         ans ++;
    //                     }
    //                 }
    //             }
    //         }
    //     }

    //     return ans;
    // }


    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {

        int ans = 0;

        HashMap<Integer, Integer> sum12 = new HashMap<>();

        // divide 4 arrays into 2 partitions which decrease the complexity to n^2
        // cache the twoSum results, then full scan the other two arrays
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int twoSum = nums1[i] + nums2[j];
                if (sum12.containsKey (twoSum)) {
                    sum12.put(twoSum, sum12.get(twoSum) + 1);
                }else {
                    sum12.put(twoSum, 1);
                }
            }
        }


        for (int k = 0; k < nums3.length; k++) {
            for (int l = 0; l < nums4.length; l++) {
                int target = 0 - nums3[k] - nums4[l];

                if (sum12.containsKey(target)) {
                    ans += sum12.get(target);
                }
            }
        }

        return ans;
    }
}

LeetCode 383.赎金信

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
class Solution {
    // public boolean canConstruct(String ransomNote, String magazine) {
    //     HashMap<Character, Integer> charRecord = new HashMap<>();
        
    //     for (int i = 0; i < magazine.length(); i++) {
    //         char c = magazine.charAt(i);
    //         if (charRecord.containsKey(c)) {
    //             charRecord.put(c, charRecord.get(c) + 1);
    //         }else {
    //             charRecord.put (c, 1);
    //         }
    //     }

    //     for (int i = 0; i < ransomNote.length(); i++) {
    //         char c = ransomNote.charAt(i);

    //         if (charRecord.containsKey(c)) {
    //             charRecord.put(c, charRecord.get(c) - 1);
    //         }else {
    //             charRecord.put (c, -1);
    //         }
    //     }

    //     for (Character c : charRecord.keySet()) {
    //         if (charRecord.get(c) < 0) {
    //             return false;
    //         }
    //     }

    //     return true;
    // }

    public boolean canConstruct(String ransomNote, String magazine) {
        int[] charRecord = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            char c = magazine.charAt(i);
            charRecord[c - 'a']++;
        }

        for (int i = 0; i < ransomNote.length(); i++) {
            char c = ransomNote.charAt(i);
            charRecord[c - 'a']--;
        }

        for (int i = 0; i < charRecord.length; i++) {
            if(charRecord[i] < 0) {
                return false;
            }
        }

        return true;
    }
}

这道题的难度不高，使用数组或者hashmap都可以，本题因为限定了两个字符串都由小写英文字母组成所以使用数组更节省空间。

LeetCode 15.三数之和

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
class Solution {

    // result in duplicate answers, for instance, [-1, 0, 1, 2, -1, -4]
    // [-1, 0, 1] and [0, 1, -1], which is hard to check

    // public List<List<Integer>> threeSum(int[] nums) {
    //     List<List<Integer>> ans = new LinkedList<>();

    //     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<Integer> res = new ArrayList<>(
    //                         Arrays.asList(nums[i], nums[j], nums[k]));
    //                     ans.add(res);
    //                 }
    //             }
    //         }
    //     }
    //     return ans;
    // }


    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> ans = new LinkedList<>();
        Arrays.sort(nums);

        // if the smallest element in the sorted array is larger than 0
        // there is no valid element groups
        if (nums[0] > 0) {
            return ans; 
        }

        
        for (int i = 0; i < nums.length; i++) {
            
            // if the same element has been checked before
            // then its corresponding left and right must 
            // be same, thus let's just skip them 
            if (i != 0 && nums[i] == nums[i - 1] ) {
                continue;
            }

            // for any fixed nums[i], use two pointer scanning the array
            // and the three sum problem is converted to finding two sum
            // which is equals to -nums[i]
            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if( sum == 0) {
                    ans.add (new LinkedList<>(
                        Arrays.asList(nums[i], nums[left], nums[right])));
                    
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }

                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }else if ( sum > 0) {
                    right--;
                }else {
                    left++;
                }
            }

        }

        return ans;
    }
}

这道题的核心难度在于去重，也就是说我们不希望有(a,b,c)这样的三元数组后，再有(b,a,c) 或者（c,a,b, 因此，在循环中我们希望始终保持循环下标间的顺序为 i < j < k.

由于对一个已经排序的数组寻找twoSum的问题可以使用双指针相向遍历的方式解决，因此，考虑通过外层循环固定一个元素，然后在内层循环使用双指针。

需要注意的是，对于a的去重需要check a之前的一位元素是否与其相等，如果相等的话跳过这次循环。因为a确定的情况下，bc是固定的，如果不跳过此次循环则会引入重复元组。对于bc而言，去重的原因和操作也是类似的。

LeetCode 18.四数之和

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
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new LinkedList<>();

        Arrays.sort(nums);

        if ( nums.length < 4) {
            return ans;
        }

        for (int i = 0; i < nums.length; i++) {

            // if nums[i] is larger than target and not negative
            // no need checking the left number
            if (nums[i] > target && nums[i] >= 0){
                break;
            }
						
            if (i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
						
            for (int j = i + 1; j < nums.length; j++) {
                
                if (nums[i] + nums[j] > target && nums[i] >= 0) {
                    break;
                }
								
              	// if and only if j > i + 1 && nums[j] == left element
                // should we skip it, as there may be a group [2,2,2,2] 
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                int left = j + 1; 
                int right = nums.length - 1;

                while ( left < right) {

                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    }else {

                        ans.add (new LinkedList<>(
                            Arrays.asList(nums[i], nums[j], nums[left], nums[right])));

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

                        while(left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }

                        left++;
                        right--;
                    }

                }
            }
        }

        return ans;
    }
}

和三数之和类似，多了一些pruning的判断，以及注意第二层循环j的去重。