【代码随想录】

数组

2. 二分查找

力扣题目链接

前提：

1. 有序数组
2. 数组中无重复元素

代码：

（版本一）左闭右闭区间

class Solution {
    public int search(int[] nums, int target) {
        //当 target 小于nums的最小值 或 大于nums的最大值时，直接返回-1
        if(target < nums[0] || target > nums[nums.length - 1])
			return -1;
		int left = 0, right = nums.length - 1, mid;
		while(left <= right) {
			mid = left + ((right- left) >> 1);
			if(nums[mid] == target)
				return mid;
			else if(nums[mid] > target)
				right = mid - 1;
			else
				left = mid + 1;
		}
		return -1;
    }
}

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

（版本二）左闭右开区间

class Solution {
    public int search(int[] nums, int target) {
        //当 target 小于nums的最小值 或 大于nums的最大值时，直接返回-1
        if(target < nums[0] || target > nums[nums.length - 2])
			return -1;
		int left = 0, right = nums.length - 1, mid;
		while(left < right) {
			mid = left + ((right- left) >> 1);
			if(nums[mid] == target)
				return mid;
			else if(nums[mid] > target)
				right = mid;
			else
				left = mid + 1;
		}
		return -1;
    }
}

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

3. 移除元素

力扣题目链接

代码：

双指针法（快慢指针法）

class Solution {
    public int removeElement(int[] nums, int val) {
        int j = 0;
		for(int i = 0; i < nums.length; i++) {
			if(nums[i] != val) {
				nums[j++] = nums[i];
			}
		} 
        return j;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

4. 有序数组的平方

力扣题目链接

前提：

1. 非递减顺序 排序的整数数组

思路：
数组本身有序，平方和较大的值一定出现在两端，可以借用前面学习的双指针法。

代码：

class Solution {
    public int[] sortedSquares(int[] nums) {
		int[] result = new int[nums.length];
		int left = 0, right = nums.length - 1, index = nums.length - 1;
		while(left <= right) {
			if(nums[left] * nums[left] < nums[right] * nums[right]) {
				//大的值从后往前放
				result[index--] = nums[right] * nums[right];
				right -= 1;
			}
			else {
				result[index--] = nums[left] * nums[left];
				left += 1;
			}
		}
		return result;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

5. 长度最小的子数组

力扣题目链接

滑动窗口：
不断调节子序列的起始位置和终止位置，从而得出想要的结果。

滑动窗口三要素：

1. 窗口内是什么？
   • 满足其和 ≥ target 的长度最小的 连续 子数组。
2. 如何移动窗口的起始位置？
   • 如果当前窗口的值 ≥ target 了，窗口就要向前移动了（窗口该缩小了）。
3. 如何移动窗口的结束位置？
   • 窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

代码：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
		int left = 0, sum = 0, result = Integer.MAX_VALUE;
		for (int right = 0; right < nums.length; right++) {
			sum += nums[right];
			//如果滑动窗口内的总和大于或等于target
			while(sum >= target) {
				//更新最小子序列长度
				result = Math.min(result, right - left + 1);
				//移动滑动窗口的起始位置，缩小窗口
				sum -= nums[left++];
			}
		}
		
		return result == Integer.MAX_VALUE ? 0 : result;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)