11. 盛最多水的容器
方法：双指针
用两个指针指向「容器」的左右边界，每次移动数字较小那一侧的指针，直到两指针相遇。这样移动指针的正确性是可以保证的。
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxArea = 0;
while(left < right) {
int area = 0;
if(height[left] < height[right]) {
area = height[left] * (right-left);
left++;
} else {
area = height[right] * (right-left);
right--;
}
if(area > maxArea) maxArea = area;
}
return maxArea;
}
15. 三数之和
给定一个数组，找出所有和为零的三元组。
方法：双指针
先把数组从小到大排序，然后在遍历数组时 for(int i = 0; i < nums.length; i++)，对于每一个 i ，用两个指针分别指向 i+1 位置和最后一个元素的位置。目的是利用这两个指针找到和为 -nums[i] 的两个元素。
List<List<Integer>> threeSum(int[] nums) {
int len = nums.length;
List<List<Integer>> result = new ArrayList<>();
if(len < 3) return result;
Arrays.sort(nums); // O(nlogn)
for(int i = 0; i < len; i++) {
if(nums[i] > 0) break; // 注意是排好序的
if(i > 0 && nums[i] == nums[i-1]) continue; // 去掉重复情况
int targetSum = -nums[i];
int left = i+1, right = len-1;
while(left < right) {
if(nums[left] + nums[right] == targetSum) {
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
// 移动两个指针，并保证移动后所指元素不和之前重复
left++;
right--;
while(left < right && nums[left] == nums[left-1]) left++;
while(left < right && nums[right] == nums[right+1]) right--;
} else if(nums[left] + nums[right] < targetSum) {
left++;
} else {
right--;
}
} // end of while
} // end of for
return result;
}
75. 颜色分类
数组中包含 0, 1, 2 三种数字，将它排序，使得所有 0 在最前面，接着是所有 1 。
方法一：单指针
维护一个指向最后一个 0 的指针，初始值为 0 ，遍历数组，将所有 0 与指针位置的元素交换；然后再遍历一遍，将所有的 1 与指针位置的元素交换（此时指针变成指向最后一个 1 的指针）。
void sortNums(int[] nums) {
int ptr = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] == 0) {
nums[i] = nums[ptr];
nums[ptr] = 0;
ptr++;
}
}
for(int i = ptr; i < nums.length; i++) {
if(nums[i] == 1) {
nums[i] = nums[ptr];
nums[ptr] = 1;
ptr++;
}
}
}
方法二：双指针
使用的指针和方法一类似，只是添加一个指向 1 序列结尾的指针 p1。遍历过程中，每发现一个 1 ，就将这个 1 和 p1 位置交换，然后 p1++；每发现一个 0 ，如果当前 p0 在 p1 前面，说明 p0 当前所指为 1 ，那么直接将遍历位置 i 的 0 和 p0 交换后， i 位置的 1 还需要与 p1 位置进行一次交换。然后 p0 和 p1 需要同时后移一位。
void sortNums(int[] nums) {
int p0 = 0, p1 = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] == 1) {
nums[i] = nums[p1];
nums[p1] = 1;
p1++;
} else if (nums[i] == 0) {
nums[i] = nums[p0];
nums[p0] = 0;
if(p0 < p1) {
nums[i] = nums[p1];
nums[p1] = 1;
}
p0++;
p1++;
}
}
}
713. 乘积小于 K 的子数组
给定一个正整数组和一个目标值，求出满足 product < target 的子数组数量。
方法：双指针（滑动窗口）
用 right 指针枚举每一个元素，同时计算乘积；每轮枚举中，令 left = 0 ，不断向右移动左指针，直到乘积小于 target 。位于这个区间的子数组的乘积就小于 target，这个子数组的子数组个数为 right - left + 1 。
int subarrayProductLessThanK(int[] nums, int k) {
if(k <= 1) return 0;
int left = 0, product = 1;
int result = 0;
for(int right = 0; right < nums.length; right++) {
product *= nums[right];
// 找到以 right 结尾的乘积小于 k 的区间
while(product >= k) {
product /= nums[left];
left++;
}
result += (right - left + 1);
}
return result;
}
202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
方法一：使用 HashSet 记录出现过的平方和
class Solution {
public boolean isHappy(int n) {
HashSet<Integer> set = new HashSet<>();
int sum = getSumOfSquares(n);
while (sum != 1) {
if (set.contains(sum)) {
return false;
}
set.add(sum);
sum = getSumOfSquares(sum);
}
return true;
}
int getSumOfSquares(int n) {
int sum = 0;
while (n > 0) {
int cur = n % 10;
sum += cur * cur;
n /= 10;
}
return sum;
}
}
方法二：快慢指针
可以将每个平方和视为一个结点，初始状态下慢指针指向原始数 n，快指针指向该数的平方和 getSumOfSquares(n) ，然后慢指针每次移动一步：getSumOfSquares(slow) ，快指针每次移动两步：getSumOfSquares(getSumOfSquares(fast)) ，如果存在循环，两个指针最终会相遇。
public boolean isHappy(int n) {
int slow = n;
int fast = getSumOfSquares(n);
while (fast != 1 && slow != fast) {
slow = getSumOfSquares(slow);
fast = getSumOfSquares(getSumOfSquares(fast));
}
return fast == 1;
}