LeetCode数组题
参考链接
代码随想录
讲解视频链接
数组题
1、(两数之和)给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
思考点：
- 为什么要把数组下标作为value，值作为key？
map.containsKey检查是否存在这个key，所以将值作为key
//暴力法
class Solution {
public int[] twoSum(int[] nums, int target) {
int length = nums.length;
int i,j;
for (i = 0;i<length;i++){
for(j = i+1;j<length;j++){
if(nums[i] + nums[j] == target){
return new int[]{i, j};
}
}
}
return null;
}
}
//哈希表法
class Solution {
public int[] twoSum(int[] nums, int target) {
// 创建一个 HashMap 用于存储值 -> 索引的映射
HashMap<Integer,Integer> map = new HashMap<>();
//遍历数组
for (int i =0;i<nums.length;i++){
int complement = target - nums[i]; // 计算目标值需要的另一个数
// 检查 Map 中是否已存在所需的数
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i}; // 返回两个索引
}
// 当前值存入 Map
map.put(nums[i], i);
}
throw new IllegalArgumentException("No solution found");
}
}
704、给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。(二分法、有序、无重复元素)
思考点：
- 左闭右闭和左开右闭的核心思想应该是
区间合法性——在设置循环条件时，是否取等号取决于它能否取到等号，right取值也是同理
2.说明：当左闭右开时，right要取值为nums.length，如果取nums.length-1，那么只有一个元素的情况，怎么取左闭右开呢？
//左闭右闭写法
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int middle = left + (right - left) / 2; // 防止溢出
if (nums[middle] > target) {
// 在左侧
right = middle - 1;
} else if (nums[middle] < target) {
// 在右侧
left = middle + 1;
} else {
// 找到目标值
return middle;
}
}
// 未找到目标值，返回 -1
return -1;
}
}
//左闭右开
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int middle = left + (right - left) / 2; // 防止溢出
if (nums[middle] > target) {
// 在左侧
right = middle ;
} else if (nums[middle] < target) {
// 在右侧
left = middle + 1;
} else {
// 找到目标值
return middle;
}
}
// 未找到目标值，返回 -1
return -1;
}
}
27、 移除元素
1.实际这个问题是考双指针解法定义快慢指针
快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
慢指针：指向更新 新数组下标的位置
//暴力解法：一个for循环遍历数组元素 ，第二个for循环更新数组
//找到val值位置，将其后元素往前移动一位
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public int removeElement(int[] nums, int val) {
int size = nums.length;
for (int i =0;i<size;i++){
if(nums[i]==val){
for(int j = i +1;j< size;j++){
nums[j-1] = nums[j];
}
i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
size--; // 此时数组的大小-1
}
}
return size;
}
}
//双指针法
class Solution {
public int removeElement(int[] nums, int val) {
int slow = 0;
for (int fast = 0;fast< nums.length; fast++){
if( nums[fast] != val){
nums[slow] = nums[fast];
slow ++;
}
}
return slow;
}
}
977、 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
思考点:
1.数组有序，且最大值出现在数组的两端，可以考虑用双指针法，这里是重点考虑结果集也需要一个指针k指向结果集终止位置，不能依靠fast指针进行填充，因为当出现slow指针数平方大于fast时，fast位置是不变的，会导致结果集同一位置覆盖赋值。
class Solution {
public int[] sortedSquares(int[] nums) {
int right = nums.length - 1;
int left = 0;
int[] result = new int[nums.length];
int index = result.length - 1;
while (left <= right) {
if (nums[left] * nums[left] > nums[right] * nums[right]) {
// 正数的相对位置是不变的， 需要调整的是负数平方后的相对位置
result[index--] = nums[left] * nums[left];
++left;
} else {
result[index--] = nums[right] * nums[right];
--right;
}
}
return result;
}
}
209.长度最小的子数组
思考点：循环索引下标使用的是终止位置，如果使用起始位置其实和暴力解法无异。
//暴力解法：result设置一个很大的数，防止就算整个序列相加都无法满足条件
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result = nums.length + 1;//设置为最大值,防止不存在符合条件的子数组
int sum = 0; // 子序列的数值之和
int subLength = 0; // 子序列的长度
for(int i = 0;i<nums.length;i++){
sum =0;
for(int j=i;j<nums.length;j++){
sum +=nums[j];
if(sum>=target){
subLength = j-i+1;
result = result < subLength? result:subLength;
}
}
}
// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
return result == nums.length + 1 ? 0 : result;
}
}
//滑动窗口
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result = nums.length + 1;//设置为最大值,防止不存在符合条件的子数组
int sum = 0; // 子序列的数值之和
int subLength = 0; // 子序列的长度
int start = 0;
for(int end = 0;end<nums.length;end++){
sum += nums[end];
while(sum >=target){
subLength = end - start + 1;
result = result < subLength? result:subLength;
sum -= nums[start];
start++;
}
}
return result == nums.length + 1 ? 0 : result;
}
}
59、螺旋矩阵：给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
思考点：确定循环不变量原则，保持一个区间；每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。
class Solution {
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
int loop;
int startx = 0; // 起始 x 坐标
int starty = 0; // 起始 y 坐标
int offset = 1; // 控制每一圈终止位置
int count = 1; // 用于计数自增
// 确定圈数
if (n % 2 == 1) {
loop = n / 2 + 1;
} else {
loop = n / 2;
}
while (loop-- > 0) {
int i = startx; // 当前层的起始行
int j = starty; // 当前层的起始列
// 从左到右填充
for (; j < n - offset; j++) {
matrix[startx][j] = count++;
}
// 从上到下填充
for (; i < n - offset; i++) {
matrix[i][j] = count++;
}
// 从右到左填充
for (; j > starty; j--) {
matrix[i][j] = count++;
}
// 从下到上填充
for (; i > startx; i--) {
matrix[i][j] = count++;
}
// 更新边界
offset++;
startx++;
starty++;
// 如果 n 是奇数，填充中心点
if (n % 2 == 1) {
matrix[n / 2][n / 2] = count;
}
}
return matrix;
}
}
58、区间和：第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。输出每个指定区间内元素的总和。
思考点:
- 用hasNextInt来循环获取输入值
- 前缀和 在涉及计算区间和的问题时非常有用，重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数。
- 要统计 vec[i] 这个数组上的区间和。先做累加，即 p[i] 表示 下标 0 到 i 的 vec[i] 累加 之和。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] vec = new int[n];
int[] p = new int[n];
int presum = 0;
for (int i =0;i<n ;i++){
vec[i] = scanner.nextInt();
presum += vec[i];
p[i] = presum;
}
while(scanner.hasNextInt()){
int a = scanner.nextInt();
int b = scanner.nextInt();
if (a ==0){
System.out.println(p[b]);
}else{
System.out.println(p[b] - p[a-1]);
}
}
scanner.close();
}
}