算法日记 - Day1

算法日记 - Day1两数之和比较经典的题目 两数之和分析题目找出数组中ab target的两个值有且只有一个答案 并且可以按照任意顺序。可以按照任意顺序但是返回的是下标也就是说我们排序数组还需要记录他们的初始下标位置有且只有一个答案我们找到第一个答案就可以收手了按照暴力可以解答但是复杂度是O(n^2)原因是因为我们是遍历的时候我们已经知道a因为数组无序我们不知道每个位置有什么所以我们还是从头到尾又重新遍历找有没有target - a这个值。所以我们其实有两种优化做法第一种哈希我们用哈希来记录有没有这个值。也就是把第二次遍历省下了时间复杂度是O(n)。如下publicint[]twoSum(int[]nums,inttarget){MapInteger,IntegermapnewHashMap();for(inti0;inums.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[][]arrnewint[nums.length][2];// 保存值和原始下标for(inti0;inums.length;i){arr[i][0]nums[i];arr[i][1]i;}// 按值排序Arrays.sort(arr,Comparator.comparingInt(a-a[0]));intleft0;intrightnums.length-1;while(leftright){intsumarr[left][0]arr[right][0];if(sumtarget){returnnewint[]{arr[left][1],arr[right][1]};}elseif(sumtarget){left;}else{right--;}}returnnull;}字母异位词分组字母异位词分组这个题思路就是你要判断多个字符串数组是不是字母异位词那就得把每个字符串数组排成某个顺序看看有哪些字符串数组排好后也符合这个顺序他们就组成字母异位词。因为都是小写字母所以正好可以把字符串转为数组再进行排序然后利用哈希表存储同类结果即可。publicListListStringgroupAnagrams(String[]strs){MapString,ListStringhashMapnewHashMap();for(Stringstr:strs){char[]charArraystr.toCharArray();Arrays.sort(charArray);StringkeynewString(charArray);if(!hashMap.containsKey(key)){ListStringvaluenewArrayList();value.add(str);hashMap.put(key,value);}else{hashMap.get(key).add(str);}}returnnewArrayList(hashMap.values());}最长连续序列最长连续序列题目说了没排序但是又说要用O(n)时间复杂度解答那说明我们不能排序了连续最长序列如果我们想知道数字5所在最长序列那我们就得知道有没有小于它的 234有没有大于它的 678。所以我们可以做哈希知道哪些数存不存在了。就容易找最长连续序列了。有个小点可以优化比如一个最长序列是4 5 6 7 8你判断 5 最长序列的时候你判断它有 4 有 678最长连续序列的长度是 5你判断 6 最长序列的时候又判断它有 45有 78最长连续序列的长度是 5是不是有点重复毕竟是同一个最长序列你这样搞。我们可以怎么做呢固定一端比如如果发现某个值(4)没有紧挨着小于它的我就去找挨着大于它的那这样4因为没有3所以以它为中心找5678。但是5678不行直接跳过。或者同样固定右端如果发现某个值(8)没有紧挨着大于它的就跳过。本质上利用序列唯一入口避免重复遍历。publicintlongestConsecutive(int[]nums){SetIntegernumsSetnewHashSet();for(intnum:nums){numsSet.add(num);}if(nums.length0)return0;intlongest1;for(intnum:numsSet){intcurrentLength1;if(numsSet.contains(num-1)){continue;}intcurrnum;while(numsSet.contains(curr))currentLength;longestMath.max(currentLength,longest);}returnlongest;}