数组

1: 1. 两数之和
2: 49. 字母异位词分组

1 - 1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。

题意:

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

难度:

中等

示例:

解析:

我们可以用双指针遍历两遍数组

 for(int add = 0; add < length; add++){
            for(int pair = add + 1; pair < length; pair++ ){
                if(nums[add] +nums[pair] == target){
                    int[] result = new int[]{add, pair};
                    return result;
                }
            }
}

但是复杂度达到 O(n^2), 运行时间会很长

主要耗时的步骤在查找数组上, 在第二次循环中我们重复查找了一些元素可以把元素放入哈希表中, 减少查询复杂度

简单建个模

1.drawio.png

class Solution {

    public int[] twoSum(int[] nums, int target) {

       //但是遍历数组的方法太麻烦, 我们换用查找复杂度为 O1 的哈希

       //哈希表存储当前索引和预期值

       HashMap<Integer, Integer> map = new HashMap<>();

       int length = nums.length;

       for(int value = 0; value < length; value++){

        //补数, 我们根据补数来查找索引

        int completement = target - nums[value];

        //先查找是否存在, 存在就直接返回

         //匹配

         if(map.containsKey(completement)){

            int[] result = new int[]{value, map.get(completement)};

            return result;

         }

        //不存在, 放入map里面

        map.put(nums[value], value);

    }

       return null;

    }

}

2 - 49. 字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。

题意:

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

难度:

中等

示例:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]

解析:

String 排序 String 中可以转为 Array 数组, 根据比较器实现自然排序

方法为 sort();

2.drawio.png

流程如上, 解释一下

对于数组的每一个元素, 转为 Array 数组并调用排序方法排序在哈希表中做快速查询, 哈希表存储有序数组和原数组集合, 返回原数组集合即可

import java.util.*;

  

public class Solution {

    public List<List<String>> groupAnagrams(String[] strs) {

        // 哈希表存储排序后的字符串作为键，异位词作为值

        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {

            // 将字符串转换为字符数组并排序

            char[] chars = s.toCharArray();

            Arrays.sort(chars);

            // 排序后的字符数组作为键

            String sortedStr = new String(chars);

            // 如果该键不存在，初始化一个新的列表

            map.putIfAbsent(sortedStr, new ArrayList<>());

            // 将原始字符串加入到对应的列表中

            map.get(sortedStr).add(s);

        }

        // 返回所有的异位词组

        return new ArrayList<>(map.values());

    }

}