LeetCode：数组专题
数组专题
有关数组的一些 leetcode 题，在此做一些记录，不然没几天就忘光光了
- 二分查找
- 双指针
- 滑动窗口
- 前缀和/差分数组
本文内容摘录自公众号labuladong中有关二分查找的文章
总结
总体框架
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}寻找一个数（基本的二分搜索）
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意1
while(left <= right) { // <= 注意2
int mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意3
else if (nums[mid] > target)
right = mid - 1; // 注意4
}
return -1;
}寻找左侧边界的二分搜索
写法1：
int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length; // 注意while (left < right) { // 注意 int mid = (left + right) / 2; if (nums[mid] == target) { right = mid; // 注意：找到了后没有返回，而是继续寻找 } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; // 注意 } } // 返回方式1：这样返回的意思就是返回了比target小的个数 return left; // 返回方式2： // target 比所有数都大 if (left == nums.length) return -1; // 类似之前算法的处理方式 return nums[left] == target ? left : -1;}
写法2：
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜索区间变为 [mid+1, right] left = mid + 1; } else if (nums[mid] > target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
} else if (nums[mid] == target) {
// 收缩右侧边界
right = mid - 1;
}
}
// 检查出界情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
寻找右侧边界的二分查找
写法1：
int right_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0, right = nums.length;while (left < right) { int mid = (left + right) / 2; if (nums[mid] == target) { left = mid + 1; // 注意：能找到右边界，没有立即返回，而是继续向右搜索 } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; } } // 返回方式1：返回了小于等于target的个数 return left - 1; // 注意 // 返回方式2： if (left == 0) return -1; return nums[left-1] == target ? (left-1) : -1;}
写法2：
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 这里改成收缩左侧边界即可
left = mid + 1;
}
}
// 这里改为检查 right 越界的情况，见下图
if (right < 0 || nums[right] != target)
return -1;
return right;
}
逻辑统一
// 寻找一个数
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] == target) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}
// 寻找左侧边界的二分查找
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，锁定左侧边界
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
// 寻找右侧边界的二分查找
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，锁定右侧边界
left = mid + 1;
}
}
// 最后要检查 right 越界的情况
if (right < 0 || nums[right] != target)
return -1;
return right;
}题目
875. 爱吃香蕉的珂珂
public int minEatingSpeed(int[] piles, int H) {
// piles 数组的最大值
int max = getMax(piles);
// 若：for(int k=1; k < max; k++){...}会有案例超时
// 通过二分法优化：寻找最小速度，就是寻找左侧边界
int left = 1, right = max - 1;
while(left <= right){
// 这样计算mid是为了防止溢出
int mid = left + (right - left) / 2;
// 以 speed 是否能在 H 小时内吃完香蕉
if(canFinish(piles, mid, H)){
right = mid-1;
}else{
left = mid+1;
}
}
// 最终结果就是返回最大值
return left;
}
private int getMax(int[] piles){
int max = piles[0];
for(int i=1; i<piles.length; i++){
if(max < piles[i]){
max = piles[i];
}
}
return max;
}
private boolean canFinish(int[] piles, int speed, int H){
int time = 0;
for(int n: piles){
time += n/speed + (n%speed == 0 ? 0: 1);
if(time > H){
return false;
}
}
return time <= H;
}1011. 在 D 天内送达包裹的能力
// 最小的装在量为能装上最大的货物 最大的装载量就是全部都能装上
int max = 0;
int total = 0;
for(int i=0; i<weights.length; i++){
total += weights[i];
if(max < weights[i]){
max = weights[i];
}
}
int left = max, right = total;
while(left <= right){
// 目前闲置能装的量
int mid = left + (right - left)/2;
// 判断是否能装完
if(isFinish(weights, mid, D)){
right = mid - 1;
}else{
left = mid + 1;
}
}
return left;
}
private boolean isFinish(int[] weights, int load, int D){
int one = 0;
int cost = 1;
for(int i=0; i<weights.length; i++){
one += weights[i];
if(one > load){
one = weights[i];
cost += 1;
}
}
return cost <= D;
}这部分内容主要参考的是公众号 labuladong，中的文章双指针技巧汇总
总结
快慢指针
判断链表中是否有环
// 快慢指针法 public boolean hasCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next!=null){ fast = fast.next.next; // 快指针走两步 slow = slow.next; // 慢指针走一步 if(fast == slow){ return true; } } return false; }已知链表中含有环，返回这个环的起始位置
在链表专题已经提及过：142. 环形链表 II
public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next;
} return null; }if(fast == slow){ // 说明此时有环存在，当其中一个节点回到头结点 fast = head; // 继续一步一步走，直到相遇，此时就是入环的节点 while(fast != slow){ fast = fast.next; slow = slow.next; } return slow; }寻找链表的中点
类似上面的思路，快指针走两步，慢指针走一步，当快指针指向链表末尾时，慢指针此时就指向链表的中间节点，需要注意的是链表节点的个数为奇数偶数的情况
public boolean hasCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next!=null){ fast = fast.next.next; // 快指针走两步 slow = slow.next; // 慢指针走一步 } // 需要注意的是： // 当链表节点个数为奇数时，就是中间节点 // 而当为偶数时，slow指向的是考后边的那个节点 return slow; }寻找链表的倒数第 k 个元素
让快指针先走 k 步，然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时，慢指针所在的位置就是倒数第 k 个链表节点
// 方法2：双指针，指针1先走k，然后指针1,2一起走，指针1走到末尾后，返回指针2，指针2的距离即为：size-k public int kthToLast(ListNode head, int k) { if(head == null){ return 0; } ListNode node1 = head; ListNode node2 = head; // 指针1先走k步 while(k-- != 0){ node1 = node1.next; } while(node1 != null){ node2 = node2.next; node1 = node1.next; } return node2.val; }
左右指针
二分查找
两数之和
// 二分法来一波 public int[] twoSum(int[] numbers, int target) { int left = 0; int right = numbers.length - 1; while(left < right){ int sum = numbers[left] + numbers[right];
} return new int[]{-1, -1}; }if(sum == target){ return new int[]{left+1, right+1}; }else if(sum < target){ left ++; }else if(sum > target){ right --; }反转数组
void reverse(int[] nums) { int left = 0; int right = nums.length - 1; while (left < right) { // swap(nums[left], nums[right]) int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } }滑动窗口算法
直接见下面
题目
26. 删除排序数组中的重复项
// 快慢指针去重
public int removeDuplicates(int[] nums) {
if(nums.length <= 1){
return nums.length;
}
int slow = 0;
int fast = 1;
while(fast < nums.length){
if(nums[fast] != nums[slow]){
nums[++slow] = nums[fast];
}
fast++;
}
return slow+1;
}83. 删除排序链表中的重复元素
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return head;
}
ListNode ans = new ListNode(-1);
ans.next = head;
// 双指针，一个走在前一个走在后
ListNode fast = head.next;
ListNode slow = head;
while(fast != null){
if(fast.val != slow.val){
slow.next = fast;
slow = slow.next;
}
fast = fast.next;
}
// 这里必须断开连接
slow.next = null;
return ans.next;
}27. 移除元素
public int removeElement(int[] nums, int val) {
if(nums.length == 0){
return nums.length;
}
int slow = 0;
int fast = 0;
while(fast < nums.length){
if(nums[fast] != val){
nums[slow] = nums[fast];
slow ++;
}
fast ++;
}
return slow;
}283. 移动零
public void moveZeroes(int[] nums) {
if(nums.length == 0){
return;
}
int fast = 0;
int slow = 0;
while(fast < nums.length){
if(nums[fast] != 0){
nums[slow] = nums[fast];
slow++;
}
fast ++;
}
while(slow < nums.length){
nums[slow] = 0;
slow++;
}
}总结
滑动窗口算法：维护一个窗口，不断滑动，然后更新答案
框架
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for(char c: t.toCharArray()){
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
// 右移窗口
right++;
// 进行窗口内数据的一系列更新 [mark：和下面一个mark处的代码基本一致]
...
/*** debug 输出的位置 ***/
System.out.println("window: [" + left + "," + right +")");
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s.charAt(left);
// 左移窗口
left++;
// 进行窗口内数据的一系列更新 [mark：和上面一个mark处的代码基本一致]
...
}
}
}使用时只需要思考以下四个问题：
当移动
right扩大窗口，即加入字符时，应该更新哪些数据？什么条件下，窗口应该暂停扩大，开始移动
left缩小窗口？当移动
left缩小窗口，即移出字符时，应该更新哪些数据？我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
题目
套用上述模版给出两个题目，好好体会
76. 最小覆盖子串
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for(char c: t.toCharArray()){
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
// 记录最小覆盖子串的起始索引及长度
int start = 0, len = s.length()+1;
while(right < s.length()){
// c 是将移入窗口的字符
char c = s.charAt(right);
// 右移窗口
right ++;
// 进行窗口内数据的一系列更新
if(need.containsKey(c)){
window.put(c, window.getOrDefault(c, 0) + 1);
if(window.get(c).equals(need.get(c))){
valid++;
}
}
// 判断左侧窗口是否要收缩
while(valid == need.size()){
// 在这里更新最小覆盖子串
if(right - left < len){
start = left;
len = right - left;
}
// d 是将移出窗口的字符
char d = s.charAt(left);
left ++;
// 进行窗口内数据的一系列更新
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d))){
valid --;
}
window.put(d, window.get(d)-1);
}
}
}
return len == s.length()+1 ? "" : s.substring(start, start+len);
}567. 字符串的排列
public boolean checkInclusion(String s1, String s2) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for(char c: s1.toCharArray()){
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
while (right < s2.length()) {
// c 是将移入窗口的字符
char c = s2.charAt(right);
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
if(need.containsKey(c)){
window.put(c, window.getOrDefault(c, 0) + 1);
if(window.get(c).equals(need.get(c))){
valid++;
}
}
// 是否有这个排列：长度相等时进可以判断了
while((right-left) >= s1.length()){
// 在这里判断是否找到了合法的子串
if(valid == need.size()){
return true;
}
// 不等则左移窗口
// d 是将移出窗口的字符
char d = s2.charAt(left);
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d))){
valid --;
}
window.put(d, window.get(d) - 1);
}
}
}
return false;
}438. 找到字符串中所有字母异位词
public List<Integer> findAnagrams(String s, String p) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for(char c: p.toCharArray()){
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
List<Integer> res = new LinkedList<>();
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
if(need.containsKey(c)){
window.put(c, window.getOrDefault(c, 0) + 1);
if(window.get(c).equals(need.get(c))){
valid++;
}
}
// 判断左侧窗口是否要收缩
while ((right-left) >= p.length()) {
if(valid == need.size()){
res.add(left);
}
// d 是将移出窗口的字符
char d = s.charAt(left);
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d))){
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return res;
}3. 无重复字符的最长子串
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int len = 0;
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
// 进行窗口内数据的一系列更新
if(window.getOrDefault(c, 0) < 1){
// 没有重复的时候的情况：右移窗口
right++;
window.put(c, window.getOrDefault(c, 0)+1);
if(right - left > len){
len = right - left;
}
}else{
// 一旦出现重复的时候：开始移左窗口
char d = s.charAt(left);
left++;
window.put(d, window.get(d) - 1);
}
}
return len;
}前缀和
前缀和数组：一个数组的前n个元素的和而组成的数组，主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。
// 例如有一个数组 nums:[1,1,1] 其前缀和为：[0,1,2,3]
int n = nums.length;
// 前缀和数组
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++)
preSum[i + 1] = preSum[i] + nums[i];案例题目：560. 和为K的子数组
public int subarraySum(int[] nums, int k) {
int n = nums.length;
// 前缀和数组
int[] preSum = new int[n+1];
preSum[0] = 0;
for(int i=0; i<n; i++){
preSum[i+1] = preSum[i] + nums[i];
}
int ans = 0;
// 穷举所有情况
for(int i=0; i<n; i++){
for(int j=i; j<n; j++){
if(k == preSum[j+1]- preSum[i]){
ans++;
}
}
}
return ans;
}
// 优化：k == preSum[j+1]- preSum[i] ---> preSum[j+1] - k = preSum[i]
public int subarraySum(int[] nums, int k) {
int n = nums.length;
//map: 前缀和 -> 该前缀和出现的次数
Map<Integer, Integer> preSum = new HashMap<>();
// base case
preSum.put(0, 1);
int ans=0, sum_0_i = 0;
for(int i=0; i<n; i++){
// 每个元素对应一个“前缀和”
sum_0_i += nums[i];
// 根据当前“前缀和”，在 map 中寻找「与之相减 == k」的历史前缀和
// [0...i] - [0...j] = k --> [j...i]是满足的
int sum_0_j = sum_0_i - k;
if(preSum.containsKey(sum_0_j)){
ans += preSum.get(sum_0_j);
}
preSum.put(sum_0_i, preSum.getOrDefault(sum_0_i, 0) + 1);
}
return ans;
}差分数组
差分数组：就是数组中一个元素和前一个元素的差
int[] diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
// 根据差分数组返回到原数组
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}这样构造差分数组diff，就可以快速进行区间增减的操作，如果你想对区间nums[i..j]的元素全部加 3，那么只需要让diff[i] += 3，然后再让diff[j+1] -= 3即可：
可以把差分数组抽象成一个类
class Difference {
// 差分数组
private int[] diff;
public Difference(int[] nums) {
assert nums.length > 0;
diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
/* 给闭区间 [i,j] 增加 val（可以是负数）*/
public void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.length) {
diff[j + 1] -= val;
}
}
public int[] result() {
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
}案例题目：1109. 航班预订统计
// 暴力解题：cost 1513 ms
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] res = new int[n];
for(int i=0; i<bookings.length; i++){
int j = bookings[i][0];
int k = bookings[i][1];
for(int len=j-1; len <=k-1; len++){
res[len] += bookings[i][2];
}
}
return res;
}
// 差分数组解题：cost 3ms
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] res = new int[n];
// 差分数组
int[] diff = new int[n];
for(int[] booking: bookings){
int i = booking[0] - 1;
int j = booking[1] - 1;
int val = booking[2];
// 对区间 nums[i..j] 增加 val
diff[i] += val;
if (j + 1 < diff.length) {
diff[j + 1] -= val;
}
}
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}手机扫一扫
移动阅读更方便
你可能感兴趣的文章