力扣hot100刷题第一天

哈希

1. 两数之和

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。
在这里插入图片描述题意：从给定数组中找到两个数的和为target，返回这两个数的下标
思路：使用哈希表存储数和对应下标，遍历的同时进行寻找

代码

class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(map.containsKey(target-nums[i])){
return new int[] {i,map.get(target-nums[i])};
}
map.put(nums[i],i);
}
return null;
}

49.字母异位词分组

题目

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词是由重新排列源单词的所有字母得到的一个新单词。
在这里插入图片描述题意：给定一系列字符串，将组成相同顺序不同的字符串放在一起并返回
思路：构建异位词的key，将相同元素放在哈希表的同一个key下，然后把哈希表的values返回

代码

class Solution {
public List<List> groupAnagrams(String[] strs) {
Map<String, List> map = new HashMap<>();
for (String str : strs) {
int n = str.length();
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
List e = map.getOrDefault(key, new ArrayList<>());
e.add(str);
map.put(key, e);
}
return map.values().stream().toList();
}
}

128. 最长连续序列

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
在这里插入图片描述题意：给定数组，找出最长连续序列的长度，如5，6，7…
思路：使用set存储所有的数，然后遍历所有的数，每一次循环，检查是否存在比当前数更小的值，如果存在，直接跳过，如果不存在，则开始统计。

代码

class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
Set set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int longest = 1;
for (Integer num : set) {
if (set.contains(num - 1)) continue;//如果 set 中存在 num - 1，则跳过当前元素（这意味着当前元素不是某个连续序列的起点）。
int curLongest = 1;
while (set.contains(++num)) {
curLongest++;
longest = Math.max(longest, curLongest);
}
}
return longest;
}
}

双指针

283.移动零

题目

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
题意：将非0的数前移，其他位置置0
思路：双指针，将非0的数移动到前指针位置，结束遍历后全部填充0

代码

方法一
int index = 0;
for(int i = 0;i< nums.length;i++){
if(nums[i] != 0){
nums[index] = nums[i];
index++;
}
}
for(int i = index;i< nums.length;i++){
nums[i] = 0;
}
方法二
class Solution {
public void moveZeroes(int[] nums) {
int i = 0; //下一个非0数存放的位置
int j = 0; //当前检索的位置
while (j < nums.length) {
if (nums[j] != 0) {
nums[i] = nums[j];
i++;
}
j++;
}
while (i < nums.length) {
nums[i] = 0;
i++;
}
}
}

11.盛最多水的容器

题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
在这里插入图片描述题意：给定数组height，任选两个下标i和j，求(j-i)*min(height[i],height[j])的最大值
思路：双指针，左指针向右检索，右指针向左检索，每次只移动高度较小的那个指针，遍历过程中记录最大面积

代码

class Solution {
public int maxArea(int[] height) {
int i=0;
int j=height.length-1;
int ans = 0;
while(i<j){
ans = Math.max(ans,(j-i)*Math.min(height[i],height[j]));
if(height[i]<=height[j]){
++i;
}
else{
–j;
}
}
return ans;
}
}

15.三数之和

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
在这里插入图片描述题意：给定数组，找出任意三个数，使其和为0，三元组不能重复
思路：先排序，再使用三指针，指针i从前往后遍历，每次循环中使用双指针j和k，若当前之和小于target则右指针前移，否则左指针后移。这里的关键是需要去重。每次结果匹配后需要移动双指针时，先记录当前指针的值，然后一直移动直到数值不相等为止。

代码

class Solution {
public List<List> threeSum(int[] nums) {
List<List> res = new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
return res;
}
if(i>0&&nums[i]==nums[i-1]) continue;
int left =i+1;
int right = nums.length-1;
while(right>left){
int sum = nums[i]+nums[left]+nums[right];
if(sum>0){
right–;
}
else if(sum<0){
left++;
}
else{
res.add(Arrays.asList(nums[i],nums[left],nums[right]));
while(right>left&&nums[right]==nums[right-1]) right–;
while(right>left&&nums[left]==nums[left+1]) left++;

                right--;
                left++;

                }
           
        }
    }
    return res;
}

}

42.接雨水

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
在这里插入图片描述题意：接雨水，有点抽象
思路：先统计每一个柱子的左边和右边最高柱子的高度，用这两个高度中较低的那个减去当前柱子高度就是当前这个点能够存储的水

代码

class Solution {
public int trap(int[] height) {
int n = height.length;

    if (n == 0) return 0; // 如果数组为空，直接返回0
    
    int[] leftMax = new int[n];
    int[] rightMax = new int[n];
    
    // 计算每个位置左边的最大高度
    leftMax[0] = height[0];
    for (int i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }
    
    // 计算每个位置右边的最大高度
    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    }
    
    // 计算总的积水量
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int waterLevel = Math.min(leftMax[i], rightMax[i]);
        if (waterLevel > height[i]) {
            sum += waterLevel - height[i];
        }
    }
    
    return sum;
}

}

滑动窗口

3.无重复字符的最长字串

题目

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
在这里插入图片描述题意：找出不含重复字符的连续字串的长度
思路：双指针指向不含重复字符的连续字串的头和尾，用集合存储子串中的元素，有重复时，左指针持续右移，无重复后统计长度

代码

 // 使用 HashSet 存储当前窗口内的字符
    Set<Character> set = new HashSet<>();
    
    // 初始化左右指针和最大长度
    int left = 0, right = 0;
    int maxLength = 0;
    
    // 遍历字符串
    while (right < s.length()) {
        char currentChar = s.charAt(right);
        
        // 如果当前字符不在集合中，将其加入集合并扩展窗口
        if (!set.contains(currentChar)) {
            set.add(currentChar);
            right++;
            maxLength = Math.max(maxLength, right - left); // 更新最大长度
        } else {
            // 如果当前字符已经在集合中，收缩窗口
            set.remove(s.charAt(left));
            left++;
        }
    }
    
    return maxLength;

438.找到字符串中所有字母异位词

题目

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
在这里插入图片描述
题意：找出所有异位词
思路：维护一个固定长度的窗口，向后遍历，每前进一步就检查当前窗口是否满足条件，满足条件就记录下来

代码

  List<Integer> result = new ArrayList<>();
    
    // 如果 s 的长度小于 p 的长度，直接返回空列表
    if (s.length() < p.length()) {
        return result;
    }
    
    // 初始化字符频率数组
    int[] pCount = new int[26]; // 记录 p 中字符的频率
    int[] sCount = new int[26]; // 记录当前窗口中字符的频率
    
    // 填充 pCount 数组
    for (char c : p.toCharArray()) {
        pCount[c - 'a']++;
    }
    
    int left = 0, right = 0;
    int pLength = p.length();
    
    while (right < s.length()) {
        // 将当前字符加入窗口，并更新频率
        char currentChar = s.charAt(right);
        sCount[currentChar - 'a']++;
        
        // 如果窗口大小等于 p 的长度
        if (right - left + 1 == pLength) {
            // 比较两个频率数组是否相等
            if (matches(sCount, pCount)) {
                result.add(left); // 记录起始索引
            }
            
            // 收缩窗口，移除最左边的字符
            sCount[s.charAt(left) - 'a']--;
            left++;
        }
        
        // 扩展窗口
        right++;
    }
    
    return result;
}

// 辅助函数：比较两个频率数组是否相等
private boolean matches(int[] sCount, int[] pCount) {
    for (int i = 0; i < 26; i++) {
        if (sCount[i] != pCount[i]) {
            return false;
        }
    }
    return true;

子串

560.和为K的子数组

题目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。
子数组是数组中元素的连续非空序列。
在这里插入图片描述
题意：寻找连续子数组使其元素和为k，输出数组的个数
思路：遍历数组时计算前缀和，将前缀和出现的次数存放在哈希表中。对于遍历到下标i时，只需要知道在之前的前缀和值为prefixSum[i] - target出现的次数即可，然后把次数相加。

代码

class Solution {
public int subarraySum(int[] nums, int k) {
// 创建一个哈希表来存储前缀和及其出现的次数
Map<Integer, Integer> map = new HashMap<>();

    // 初始化前缀和为0的出现次数为1
    map.put(0, 1);
    
    int sum = 0; // 当前前缀和
    int count = 0; // 记录符合条件的子数组数量
    
    // 遍历数组中的每个元素
    for (int num : nums) {
        // 更新当前前缀和
        sum += num;
        
        // 检查是否存在前缀和 sum - k
        count += map.getOrDefault(sum - k, 0);
        
        // 更新当前前缀和的出现次数
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    
    return count;
}

}