数组去重和nsum问题及其他杂项

一、数组原地去重方法

1.1 有序数组去重

利用双指针向前滑动，不会漏掉任何一个数。

26. 删除有序数组中的重复项

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int left = 0, right = 1;
        while(right < nums.length) {
            if (nums[left] != nums[right]) {
                nums[++left] = nums[right];
            }
            right++;
        }
        return left+1;
    }
}

83. 删除排序链表中的重复元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;
    ListNode slow = head, fast = head;
    while (fast != null) {
        if (fast.val != slow.val) {
            // nums[slow] = nums[fast];
            slow.next = fast;
            // slow++;
            slow = slow.next;
        }
        // fast++
        fast = fast.next;
    }
    // 断开与后面重复元素的连接
    slow.next = null;
    return head;
}

1.2 移除元素

27. 移除元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0, right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[--right];
            } else {
                left++;
            }
        }
        return left;
    }
}

1.3 无序去重

这部分使用单调栈，暂时不讨论。

二、nSum 问题

2.1 TwoSum 核心思想

这个问题的最基本形式是这样：给你一个数组和一个整数 target，可以保证数组中存在两个数的和为 target，请你返回这两个数的索引。

比如输入 nums = [3,1,3,6], target = 6，算法应该返回数组 [0,2]，因为 3 + 3 = 6。

最简单的就是利用穷举，然后可以利用哈希表来减少时间复杂度。

假如nums 是一个排序数组，则直接利用双指针就可以解决。

1. 两数之和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


public int[] twoSum(int[] nums, int target) {
    Map<Integer,Integer> map=new HashMap<>();
    for(int i=0;i<nums.length;i++){
        int sub=target-nums[i];
        if(map.containsKey(sub)){
            return new int[]{i,map.get(sub)};
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

170. 两数之和 III - 数据结构设计（简单）

这题专注于设计这样的一个结构。当然可以用上面的hash 表来方法来实现哈希辅助的find方法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class TwoSum {
    Map<Integer, Integer> freq = new HashMap<>();

    public void add(int number) {
        // 记录 number 出现的次数
        freq.put(number, freq.getOrDefault(number, 0) + 1);
    }
    
    public boolean find(int value) {
        for (Integer key : freq.keySet()) {
            int other = value - key;
            // 情况一
            if (other == key && freq.get(key) > 1)
                return true;
            // 情况二
            if (other != key && freq.containsKey(other))
                return true;
        }
        return false;
    }
}

对于这个解法的时间复杂度呢，add 方法是 O(1)，find 方法是 O(N)，空间复杂度为 O(N)，和上一道题目比较类似。

但是对于 API 的设计，是需要考虑现实情况的。比如说，我们设计的这个类，使用 find 方法非常频繁，那么每次都要 O(N) 的时间，岂不是很浪费费时间吗？对于这种情况，我们是否可以做些优化呢？

是的，对于频繁使用 find 方法的场景，我们可以进行优化。我们可以参考上一道题目的暴力解法，借助哈希集合来针对性优化 find 方法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class TwoSum {
    Set<Integer> sum = new HashSet<>();
    List<Integer> nums = new ArrayList<>();

    public void add(int number) {
        // 记录所有可能组成的和
        for (int n : nums)
            sum.add(n + number);
        nums.add(number);
    }
    
    public boolean find(int value) {
        return sum.contains(value);
    }
}

这样 sum 中就储存了所有加入数字可能组成的和，每次 find 只要花费 O(1) 的时间在集合中判断一下是否存在就行了，显然非常适合频繁使用 find 的场景。

这里没有任何复杂的内容，主要想说明一个思想：设计算法时要时刻关注场景，针对不同的场景选择适当的数据结构也是算法设计非常重要的部分。

2.2 3 Sum 问题

首先给出 TwoSum 的排序版本，返回值（不是索引）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public List<List<Integer>> twoSum(int[] nums, int lo, int hi, int target) {
    if (nums == null || nums.length < 2)
        return null;
    List<List<Integer>> ret = new ArrayList<>();
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        int left = nums[lo], right = nums[hi];
        if (sum < target) {
            lo++;
        } else if (sum > target) {
            hi--;
        } else {
            List<Integer> list = new ArrayList<>();
            list.add(left);
            list.add(right);
            ret.add(list);
            while (lo < hi && nums[lo] == left) lo++;
            while (lo < hi && nums[hi] == right) hi--;
        }
    }
    return ret;
}

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


class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] > 0) break;
            int a = nums[i], target = -a;
            
            // Arrays.sort(temp);
            List<List<Integer>> list = twoSum(nums, i+1, n-1, target);
            if (list != null) {
                for (List object : list) {
                    object.add(a);
                    // Collections.sort(object);
                    res.add(object);
                }
            }
            while ( i < n - 1 && nums[i] == nums[i+1]) i++;
        }
        return res;
    }

    public List<List<Integer>> twoSum(int[] nums, int lo, int hi, int target) {
        if (nums == null || nums.length < 2)
            return null;
        List<List<Integer>> ret = new ArrayList<>();
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            int left = nums[lo], right = nums[hi];
            if (sum < target) {
                lo++;
            } else if (sum > target) {
                hi--;
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(left);
                list.add(right);
                ret.add(list);
                while (lo < hi && nums[lo] == left) lo++;
                while (lo < hi && nums[hi] == right) hi--;
            }
        }
        return ret;
    }
}

2.3 4 Sum 问题

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


class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < n - 3; i++) {
            // if (nums[i] > target) break;
            List<List<Integer>> list = threeSum(nums, i+1, n-1, target-nums[i]);
            if (list != null) {
                for (List object : list) {
                    object.add(nums[i]);
                    // Collections.sort(object);
                    res.add(object);
                }
            }
            while ( i < n - 1 && nums[i] == nums[i+1]) i++;
        }
        return res;
    }
    
    public List<List<Integer>> threeSum(int[] nums, int lo, int hi, int target) {
        if (hi - lo + 1 < 3)
            return null;
        List<List<Integer>> res = new ArrayList<>();
        for (int i = lo; i < hi - 1; i++) {
            // if (nums[i] > target) break;
            List<List<Integer>> list = twoSum(nums, i+1, hi, target-nums[i]);
            if (list != null) {
                for (List object : list) {
                    object.add(nums[i]);
                    // Collections.sort(object);
                    res.add(object);
                }
            }
            while ( i < hi && nums[i] == nums[i+1]) i++;
        }
        return res;
    }

    public List<List<Integer>> twoSum(int[] nums, int lo, int hi, int target) {
        if (nums == null || nums.length < 2)
            return null;
        List<List<Integer>> ret = new ArrayList<>();
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            // if (nums[lo] > target) break;
            int left = nums[lo], right = nums[hi];
            if (sum < target) {
                lo++;
            } else if (sum > target) {
                hi--;
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(left);
                list.add(right);
                ret.add(list);
                while (lo < hi && nums[lo] == left) lo++;
                while (lo < hi && nums[hi] == right) hi--;
            }
        }
        return ret;
    }
}

三、杂项

870. 优势洗牌

labuladong 题解：以田忌赛马来讲述，很形象有趣

也是用双指针，先把两个数组排序就行

 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


int[] advantageCount(int[] nums1, int[] nums2) {
    int n = nums1.length;
    // 给 nums2 降序排序
    PriorityQueue<int[]> maxpq = new PriorityQueue<>(
        (int[] pair1, int[] pair2) -> { 
            return pair2[1] - pair1[1];
        }
    );
    for (int i = 0; i < n; i++) {
        maxpq.offer(new int[]{i, nums2[i]});
    }
    // 给 nums1 升序排序
    Arrays.sort(nums1);

    // nums1[left] 是最小值，nums1[right] 是最大值
    int left = 0, right = n - 1;
    int[] res = new int[n];

    while (!maxpq.isEmpty()) {
        int[] pair = maxpq.poll();
        // maxval 是 nums2 中的最大值，i 是对应索引
        int i = pair[0], maxval = pair[1];
        if (maxval < nums1[right]) {
            // 如果 nums1[right] 能胜过 maxval，那就自己上
            res[i] = nums1[right];
            right--;
        } else {
            // 否则用最小值混一下，养精蓄锐
            res[i] = nums1[left];
            left++;
        }
    }
    return res;
}