每日一题
第一题
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 只会存在一个有效答案
说实话这个题我每次都会用不太一样的方法写，最后看一下题解想起来这个方法，最主要是这个方法相对较快。
思路：这个题是先将数组中的数据通过便利然会在便利的同时进行比较，每次都会使用Map中的方法containsKey来进行判断对应的target-nums[i]的值有没有在map中存储过，如果有的话就直接返回没有的话就会将当前的值存储到map中。
误区：很多人会想为什么不直接将数组中的所有数据都直接存储到map中这样不也可以，nonono这样是不可以的，因为数组中的数据是会重复的你如果直接全部存储进去就会出现覆盖的情况，这样最后的结果肯定不是正确的，比如你使用样例
nums=[1,2,3,3] , target = 6做一个测试如果你用直接存储的方式最后肯定是不存在结果，但是这样是存在两个数可以满足情况的。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
if(map.containsKey(target-nums[i])){//判断当前的nums[i]有无对应的数字
return new int []{i,map.get(target-nums[i])};//如果有直接返回
}
map.put(nums[i],i);//没有的话就将数据存储在map中供接下来使用
}
return new int []{0,0};
}
}
第二题
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
解释：
- 在 strs 中没有字符串可以通过重新排列来形成
"bat"。 - 字符串
"nat"和"tan"是字母异位词，因为它们可以重新排列以形成彼此。 - 字符串
"ate"，"eat"和"tea"是字母异位词，因为它们可以重新排列以形成彼此。
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]
提示：
- 1 <= strs.length <= 104
- 0 <= strs[i].length <= 100
strs[i]仅包含小写字母
这个题让我涨知识了，如果想将char[]转成字符串需要使用new String()、Arrays.toString()的方法，不能直接使用toString()去转换这样是不行了，因为直接使用toString的话返回的是地址。
思路：就是将里边的每一个字符串取出来然后进行排序，然后使用map存储，并使用containsKey校验当前是否存在，如果存在就直接存入，反之先new一下在存入，最后需要返回map中的所有value值
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map=new HashMap<>();
for(String str:strs){
char[] ch = str.toCharArray();//将String类型的转成char[]类型的
Arrays.sort(ch);//将数组内的元素排序
String str1=new String(ch);
if(!map.containsKey(str1)){//判断你是否存在，为了防止空指针
map.put(str1,new ArrayList<>());
}
map.get(str1).add(str);
}
return new ArrayList<>(map.values());
}
}
第三题
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
示例 3：
输入：nums = [1,0,1,2]
输出：3
提示：
- 0 <= nums.length <= 105
- -109<= nums[i] <= 109
思路1：这个题吧整体就是一个双指针，但是需要注意一些东西，比如在这个题目中说到不用在意是否相邻只需要连续就行，如果直接排序然后使用双指针判断连续的话就会错，所以如果想过就需要添加一个判断条件就是在排序后相邻两个数如果相同的话就需要用一个中间值去记住最后在将这个值减去。
下边的两个解法在本质上其实没有什么区别
其实这个题目我还想到了一种其他的解法，但是最后的时间复杂度一定会增加，就是使用map计算重复的数字然后将重复的数字筛选出来扔掉，只将每个数字都留下一份最后排序使用双指针。
//解法一
class Solution {
public int longestConsecutive(int[] nums) {
int maxn=1,j=0,t=0;
//这个特判其实有两种判法，一种是设置maxn的初始值为0判nums的长度为1时return 1 另一种就是代码中写的这种
if(nums.length==0)return 0;//特判
Arrays.sort(nums);//排序
for(int i=1;i<nums.length;i++){
if(nums[i]-nums[i-1]<=1){
if(nums[i]-nums[i-1]<1)t++;//计算重复的数字有几个
maxn=Math.max(maxn,i-j+1-t);//找最大值并去掉重复的数
continue;
}
j=i;
t=0;
}
return maxn;
}
}
//解法二
class Solution {
public int longestConsecutive(int[] nums) {
int maxn=1,j=0,t=0;
if(nums.length==0)return 0;
Arrays.sort(nums);
for(int i=1;i<nums.length;i++){
if(nums[i]-nums[i-1]<=1){
if(nums[i]-nums[i-1]==1) t++;
continue;
}
maxn=Math.max(maxn,t+1);
j=i;
t=0;
}
maxn=Math.max(maxn,t+1);
return maxn;
}
}