算法日记 - Day1

算法日记 - Day1

两数之和

比较经典的题目 两数之和

分析题目，找出数组中a+b = target的两个值，有且只有一个答案 ，并且可以按照任意顺序。

• 可以按照任意顺序，但是返回的是下标，也就是说我们排序数组，还需要记录他们的初始下标位置
• 有且只有一个答案，我们找到第一个答案就可以收手了

按照暴力可以解答，但是复杂度是O(n^2)，原因是因为我们是遍历的时候，我们已经知道a，因为数组无序，我们不知道每个位置有什么，所以我们还是从头到尾又重新遍历，找有没有target - a这个值。

所以我们其实有两种优化做法，第一种，哈希，我们用哈希来记录有没有这个值。也就是把第二次遍历省下了，时间复杂度是O(n)。如下

publicint[]twoSum(int[]nums,inttarget){Map<Integer,Integer>map=newHashMap<>();for(inti=0;i<nums.length;i++){if(map.containsKey(target-nums[i])){returnnewint[]{i,map.get(target-nums[i])};}else{map.put(nums[i],i);}}returnnull;}

还有一种做法，平均时间复杂度是O(nlogn)，时间复杂度主要浪费在了排序上，不如哈希。并且还需要记录原始下标，也就是借助排序后的规律，我们先取i = 0, j = nums.length - 1，如果nums[i] + nums[j] > target，那么说明答案中的[i, j]，j需要变小，如果nums[i] + nums[j] < target，那么说明答案中的[i, j]，i需要变大。
当我们算完之后再把原始的数组下标返回即可。

publicint[]twoSum(int[]nums,inttarget){int[][]arr=newint[nums.length][2];// 保存值和原始下标for(inti=0;i<nums.length;i++){arr[i][0]=nums[i];arr[i][1]=i;}// 按值排序Arrays.sort(arr,Comparator.comparingInt(a->a[0]));intleft=0;intright=nums.length-1;while(left<right){intsum=arr[left][0]+arr[right][0];if(sum==target){returnnewint[]{arr[left][1],arr[right][1]};}elseif(sum<target){left++;}else{right--;}}returnnull;}

字母异位词分组

字母异位词分组

这个题思路就是你要判断多个字符串数组是不是字母异位词，那就得把每个字符串数组排成某个顺序，看看有哪些字符串数组排好后也符合这个顺序，他们就组成字母异位词。因为都是小写字母，所以正好可以把字符串转为数组再进行排序，然后利用哈希表存储同类结果即可。

publicList<List<String>>groupAnagrams(String[]strs){Map<String,List<String>>hashMap=newHashMap<>();for(Stringstr:strs){char[]charArray=str.toCharArray();Arrays.sort(charArray);Stringkey=newString(charArray);if(!hashMap.containsKey(key)){List<String>value=newArrayList<>();value.add(str);hashMap.put(key,value);}else{hashMap.get(key).add(str);}}returnnewArrayList<>(hashMap.values());}

最长连续序列

最长连续序列

• 题目说了没排序，但是又说要用O(n)时间复杂度解答，那说明我们不能排序了
• 连续最长序列，如果我们想知道数字5所在最长序列，那我们就得知道有没有小于它的 2，3，4，有没有大于它的 6，7，8。所以我们可以做哈希，知道哪些数存不存在了。就容易找最长连续序列了。

有个小点可以优化，比如一个最长序列是4 5 6 7 8，你判断 5 最长序列的时候，你判断它有 4， 有 6，7，8，最长连续序列的长度是 5，你判断 6 最长序列的时候，又判断它有 4，5，有 7，8，最长连续序列的长度是 5，是不是有点重复，毕竟是同一个最长序列，你这样搞。我们可以怎么做呢？固定一端，比如如果发现某个值(4)没有紧挨着小于它的，我就去找挨着大于它的，那这样4因为没有3，所以以它为中心找5，6，7，8。但是5，6，7，8不行，直接跳过。或者同样，固定右端，如果发现某个值(8)没有紧挨着大于它的，就跳过。

本质上：利用序列唯一入口，避免重复遍历。

publicintlongestConsecutive(int[]nums){Set<Integer>numsSet=newHashSet<>();for(intnum:nums){numsSet.add(num);}if(nums.length==0)return0;intlongest=1;for(intnum:numsSet){intcurrentLength=1;if(numsSet.contains(num-1)){continue;}intcurr=num;while(numsSet.contains(++curr))currentLength++;longest=Math.max(currentLength,longest);}returnlongest;}