344. Reverse String

題目

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Constraints:

• 1 <= s.length <= 105
• s[i] is a printable ascii character.

解法(Java)

跟反轉陣列是一樣的概念...

Runtime: 0 ms (100%)
Memory Usage: 50.3 MB (89.31%)

class Solution {
    public void reverseString(char[] s) {
        int limit = s.length - 1;
        char temp;
        for (int i = 0; i < limit; i++, limit--) {
            temp = s[i];
            s[i] = s[limit];
            s[limit] = temp;
        }
    }
}

561. Array Partition

題目

Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

Example 1:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

Example 2:

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

Constraints:

• 1 <= n <= 10^4
• nums.length == 2 * n
• 10^4 <= nums[i] <= 10^4

解法(Java)

這題其實有兩個解法，這一種是比較多人用的，排序之後只直接取偶數索引值的元素。

而另一種感覺比較偷吃步，雖然快了一倍的時間，但實際情境下不會知道長度最大值，因此這邊就不展示了。

Runtime: 12 ms (95.47%)
Memory Usage: 44.3 MB (97.72%)

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);

        int result = 0;

        for (int i = 0, size = nums.length; i < size; i+= 2) {
            result += nums[i];
        }

        return result;
    }
}

167. Two Sum II - Input Array Is Sorted

題目

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

• 2 <= numbers.length <= 3 * 10^4
• 1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• 1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

解法(Java)

這題如果暴力解的話是可以過的，只是時間複雜度會是O(n^2)，可以用雙指針演算法去解題，從左右兩邊不斷向中間靠攏，能夠大幅減少消耗時間。

Runtime: 1 ms (100%)
Memory Usage: 45.1 MB (91.07%)

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1, sum = numbers[left] + numbers[right];

        while (sum != target) {
            if (sum > target) {
                sum = numbers[left] + numbers[--right];
            } else {
                sum = numbers[++left] + numbers[right];
            }
        }

        return new int[] {left + 1, right + 1};
    }
}

209. Minimum Size Subarray Sum

題目

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

解法(Java)

這題要用到雙指標演算法的衍生算法，稱為滑動視窗(Slide Window)演算法，相較於快慢演算法的兩個指針是一樣的速度往前，Slide Window 是根據數值的大小判斷哪一端要往前進。

Runtime: 1 ms (99.93%)
Memory Usage: 49.7 MB (100%)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, sum = 0, len = nums.length, res = len + 1;
        
        for (int right = 0; right < len; right++) {
        	sum += nums[right];
        	while (sum >= target) {
        		res = res > right - left + 1 ? right - left + 1 : res;
        		sum -= nums[left++];
        	}
        }
    	
    	return res == len + 1 ? 0 : res;
    }
}

小結

後面兩題都是Medium，需要靈活的運用雙指針演算法才能夠更快的解決題目，這邊還多認識了滑動視窗演算法，感覺刷了越多題目越要紀錄學了哪些演算法，不然學到後面忘了前面就不好了。