发表于 | 分类于

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?

解法1： O(N^2)

O(N^2)的解法和3Sum或者3Sum closest类似，但比较tricky的地方是，在用双指针left和right找到一个<target的数的时候，其实right 和left之间所有的数都满足要求（排序之后）。所以这个时候我们把right-left加入到res中，然后更新left即可。

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
public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums.length < 3) {
            return 0;
        }
        Arrays.sort(nums);
        int n = nums.length;
        int cnt = 0;
        for (int i = 0; i < n - 2; i++) {
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < target) {
                    cnt += right - left;    // trick is here
                    left++;
                } else {
                    right--;
                }
            }
        }
        return cnt;
    }
}

发表于 | 分类于

Given a sorted integer array where the range of elements are in the inclusive range [lower, upper], return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return [“2”, “4->49”, “51->74”, “76->99”].

解法1：

挺无聊的一道题，主要是corner case比较多。
算法不难，就是遍历一遍数组。找出是否是连续的数，如果不是那么补上缺少的range。
corner case有：
缺少的是一个数，不是range
两个相同的数
数字已经是Integer.MAX_VALUE，会溢出。
C++

1

Java

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
public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<String>();
        if (nums.length == 0) {
            if (lower == upper) {
                res.add(Integer.toString(lower));
            } else {
                res.add(Integer.toString(lower) + "->" + Integer.toString(upper));
            }
            return res;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (i == 0 && nums[i] > lower) {
                if (nums[i] == lower + 1) {
                    res.add(Integer.toString(lower));
                } else {
                     res.add(Integer.toString(lower) + "->" + Integer.toString(nums[i] - 1));
                }
            } else if (i != 0) {
                if (nums[i] != nums[i - 1] && nums[i] > nums[i - 1] + 1) {
                    if (nums[i] == nums[i - 1] + 2) {
                        res.add(Integer.toString(nums[i - 1] + 1));
                    } else {
                        res.add(Integer.toString(nums[i - 1] + 1) + "->" + Integer.toString(nums[i] - 1));
                    }
                }
            }
            if (i == nums.length - 1) {
                if (upper > nums[i]) {
                    if (upper == nums[i] + 1) {
                        res.add(Integer.toString(upper));
                    } else {
                        res.add(Integer.toString(nums[i] + 1) + "->" + Integer.toString(upper));
                    }
                }
            }
        }
        return res;
    }
}

发表于 | 分类于

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

解法1：

这题比较关键的是题目的条件，数字在1和n之间。那么用置换的办法可以达到复杂度的要求。对于每一个数字，如果没有重复，排序之后他应该在i+1上。
那么我们可以把每一个数字归位。要注意，如果i和j置换了，i不应该往前进而是应该停留原地（i–那行很重要）
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        // Use the condition that num in nums are between 1 and n
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != nums[nums[i] - 1]) {
                int temp = nums[i];
                nums[i] = nums[temp -1];
                nums[temp - 1] = temp;
                i--;        // very important
            }
        }
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (i != nums[i] - 1) {
                res.add(nums[i]);
            }
        }
        return res;
    }
}

发表于 | 分类于

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

More practice:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

解法1：dynamic window O(N)

动态窗口的一种应用。用左右两个指针维护一个窗口，先移动右指针直到加和>=sum, 然后在开始移动左指针，每次移动判断加和是否还满足并且更新最小的差距。
C++

1

Java

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
public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int left = 0, right = 0, n = nums.length, sum = 0;
        // left, right is a dynamic window
        int res = Integer.MAX_VALUE;
        while (right < n) {
            while (sum < s && right < n) {
                sum += nums[right++];
            }
            while (sum >= s) {
                res = Math.min(res, right - left);
                sum -= nums[left++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

用binary search的条件是数组一定是一定程度上有序的。这里把数组变成了一个累加的数组。然后对于每一个加和
sum， 寻找在之后的第一个数字k使得k>=sum+s，找到之后更新坐标。
Java

lang: java
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
public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // Create a helper array
        int n = nums.length;
        int[] helper = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            helper[i] = helper[i - 1] + nums[i - 1];
        }
        int res = Integer.MAX_VALUE;
        for (int i =  0; i < n; i++) {
            int temp = binarySearch(helper, i + 1, n, s + helper[i]);
            if (temp != -1) {
                res = Math.min(res, temp - i);
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
    private int binarySearch(int[] nums, int left, int right, int target) {
        // Find the first element in nums that is larger or equal to the target
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else if (nums[mid] >= target) {
                right = mid;
            }
        }
        if (nums[left] >= target) {
            return left;
        } else if (nums[right] >= target) {
            return right;
        } else {
            return -1;
        }
    }
}

发表于 | 分类于

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity’s label if there is a celebrity in the party. If there is no celebrity, return -1.

解法1: Greedy

这题用暴力法解的话是O(N^2)的复杂度，那么要降低复杂度只有O(N), O(logN), O(NlogN)几种。似乎binary search也不能很好解决。在这种情况下，有一类算法可能有奇效，就是greedy。
可以用greedy的题目有一类特征就是有的时候题目会告诉，如果有的话有且仅有一个解。
这里我们就先遍历一遍数组，找到一个可能为celebrity的数字。
然后再验证一遍该数字，是否满足条件，如果不满足条件，那么就说明没有celebrity。如果有，那么就是他。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution extends Relation {
    public int findCelebrity(int n) {
        int celebrity = 0;
        for (int i = 0; i < n; ++i) {
            if (knows(celebrity, i)) {
                celebrity = i;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (celebrity != i && (knows(celebrity, i) || !knows(i, celebrity))) {
                return -1;
            }
        }
        return celebrity;
    }
}

发表于 | 分类于

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]

Given target = 3, return true.

解法1：

这题有两种做法，都用到了binary search。一种只需要一次binary search，也就是下面的这种解法。但缺点是row×col可能会溢出，同时取余数的操作比较expensive。
还有一种是两次binary search。先用一次找出最后一行其中第一个数字小于target，然后再这行再用一次binary search。
C++

1

Java

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
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int start = 0, end = m * n - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int row = mid / n;
            int col = mid % n;
            if (matrix[row][col] < target) {
                start = mid;
            } else if (matrix[row][col] > target) {
                end = mid;
            } else {
                return true;
            }
        }
        if (matrix[start / n][start % n] == target || matrix[end / n][end % n] == target) {
            return true;
        }
        return false;
    }
}

发表于 | 分类于

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Write a function to determine if a given target is in the array.

The array may contain duplicates.

解法1: O(logN), worst case O(n)

当有重复值的时候，我们在判断丢弃left或者是right half的时候，如果碰到nums[mid] == nums[end]或者nums[mid] == nums[start]的时候，不能判断哪一个部分需要抛弃。这个时候只能让end–或者start–
C++

1

Java

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
public class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[mid] < nums[end]) {
                if (nums[mid] < target && nums[end] >= target) {
                    start = mid;
                } else {
                    end = mid;
                }
            } else if (nums[mid] > nums[end]) {
                if (nums[start] <= target && nums[mid] > target) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else {
                end--;  // can not remove a half
            }
        }
        if (nums[end] == target || nums[start] == target) {
            return true;
        } else {
            return false;
        }
    }
}

发表于 | 分类于

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

1
2
3
4
5
6
7
8
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解法1： O(N^3)

和3Sum一样的思路，最外层遍历第一个数，第二层遍历第二个数，之后用双指针像中间扫描。遇到加和为target的就推入list中。要注意的是需要去重。那么每一次去重的时候只需要跳过和前一个一样的数就可以了。
C++

1

Java

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
public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int n = nums.length;
        if (n < 4) {
            return res;
        }
        Arrays.sort(nums);      // need to sort first
        for (int i = 0; i < n - 3; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < n - 2; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int k = j + 1;
                int m = n - 1;
                while (k < m) {
                    while (k != j + 1 && k < m && nums[k] == nums[k - 1]) {
                        k++;    // remove duplicates
                    }
                    while (m != n - 1 && k < m && nums[m] == nums[m + 1]) {
                        m--;
                    }
                    if (k < m) {
                        int sum = nums[i] + nums[j] + nums[k] + nums[m];
                        if (sum == target) {
                            List<Integer> temp = new ArrayList<Integer>();
                            temp.add(nums[i]);
                            temp.add(nums[j]);
                            temp.add(nums[k]);
                            temp.add(nums[m]);
                            res.add(temp);
                            k++;
                            m--;
                        } else if (sum < target) {
                            k++;
                        } else {
                            m--;
                        }
                    }
                }
            }
        }
        return res;
    }
}

发表于 | 分类于

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

解法1：O(N^2)

closest转化为程序的意思就是说，需要一个var来记录每一次的sum，然后把当前的diff和之前diff来比较。
循环的时候从头开始像后循环。
C++

1

Java

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
public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int closest = 0;
        for (int i = 0; i < 3 && i < nums.length; i++) {
            closest += nums[i];
        }
        if (nums.length < 3) {
            return closest;
        }
        for (int i = 0; i < nums.length - 2; i++) {
            int j =  i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (Math.abs(sum - target) < Math.abs(closest - target)) {
                    closest = sum;
                    if (closest == target) return closest;
                }
                if (sum < target) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return closest;
    }
}

发表于 | 分类于

Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.

Example 1:

1
2
3
4
5
6
Input: candies = [1,1,2,2,3,3]
Output: 3
Explanation:
There are three different kinds of candies (1, 2 and 3), and two candies for each kind.
Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.
The sister has three different kinds of candies.

Example 2:

1
2
3
4
Input: candies = [1,1,2,3]
Output: 2
Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1].
The sister has two different kinds of candies, the brother has only one kind of candies.

Note:

The length of the given array is in range [2, 10,000], and will be even.
The number in given array is in range [-100,000, 100,000].

解法1：

有一类问题的思路是这样的：如果求最大或者最小值，先考虑一下理论上可能可以取到的值。然后再以此为突破口看看是否有思路。
这题就是这样，先想到要取n/2个数，那么最大的种类也就是n/2，不可能再大了。那么如果数组里的类别比n/2小，那么最大的值就是数组里的数的种类数。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int distributeCandies(int[] candies) {
        if (candies == null || candies.length == 0) {
            return 0;
        }
        Set<Integer> set = new HashSet<Integer>();
        for (int candy: candies) {
            set.add(candy);
        }
        return Math.min(set.size(), candies.length / 2);
    }
}