最近两天的日常题也太难了罢 今天的抄个答案放弃了 索性从头开始复习一下1 ~ 300题好了 本人末流211本科 不想考研 大一大二学习不是很用功 现在在努力追进度 脑子不好使 大家轻喷
class Solution { public int[] twoSum(int[] nums, int target) { int n = nums.length; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (nums[i] + nums[j] == target) { return new int[]{i, j}; } } } return new int[0]; } }
方法一 两次循环 时间复杂度O(N)
class Solution { public int[] twoSum(int[] nums, int target) { HashMap<Integer,Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++){ map.put(nums[i],i); } for(int j = 0; j < nums.length; j++){ if(map.containsKey(target - nums[j])&&map.get(target - nums[j])!= j){ return new int[]{j, map.get(target - nums[j])}; } } return null; } }
#1注意特殊情况 比如 [2,3] 目标是4 要避免2重复取到的情况
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode() {} 7 * ListNode(int val) { this.val = val; } 8 * ListNode(int val, ListNode next) { this.val = val; this.next = next; } 9 * } 10 */ 11 class Solution { 12 public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 13 int carry = 0; 14 int sum = 0; 15 ListNode res = new ListNode(0); 16 ListNode ans = res; 17 while(l1 != null || l2 != null){ 18 int left = l1 == null?0:l1.val; 19 int right = l2 == null?0:l2.val; 20 sum = carry + left + right; 21 res.next = new ListNode(sum%10); 22 carry = sum/10; 23 sum = sum%10; 24 res = res.next; 25 if(l1 != null) l1 = l1.next; 26 if(l2 != null) l2 = l2.next; 27 } 28 if(carry > 0){ 29 res.next = new ListNode(1); 30 } 31 return ans.next; 32 } 33 }
#2设置一个进位标志carry 两数相加和为(0, 18)之间 我们新节点的值容易理解是 % 10剩下的那个数 加上上一位的进位标志（如果上一位有进位的话）
然后如果有进位（两数之和大于10）进位也就是 /10 最多为1嘛 最后两个链表走完了判断一下最外面有没有进位 也就是类似 3 + 7 = 10的情况
然后要注意的也就是链表的转移了 等过两天链表感觉有点忘了也许会整理一下链表的题目罢
1 class Solution { 2 public int lengthOfLongestSubstring(String s) { 3 char[] str = s.toCharArray(); 4 int res = 0; 5 for(int i = 0; i < str.length; i++){ 6 HashSet<Character> set = new HashSet<>(); 7 int count = 0; 8 for(int j = i; j < str.length; j++){ 9 if(!set.contains(str[j])){ 10 count++; 11 set.add(str[j]); 12 }else{ 13 count = 0; 14 } 15 res = Math.max(res, count); 16 } 17 } 18 return res; 19 } 20 }
#3 好久之后第二次写 无脑暴力 思路没问题......但是超时了 986 / 987 个通过测试用例 时间复杂度在O(N)和O(N^2)之间吧 空间复杂度O(N) 不是很会算唉
1 class Solution { 2 public int lengthOfLongestSubstring(String s) { 3 HashSet<Character> set = new HashSet<>(); 4 int len = s.length(); 5 int res = 0, left = 0, right = 0; 6 while(left < len && right < len){ 7 if(!set.contains(s.charAt(right))){ 8 set.add(s.charAt(right++)); 9 res = Math.max(res, (right - left)); 10 }else{ 11 set.remove(s.charAt(left++)); 12 } 13 } 14 return res; 15 } 16 }
第二种方法 滑动窗口 很巧妙的地方是 用到的是 i++ 而不是 ++i 时间复杂度O(2N) === O(N)
a b c a b c a
i j
a b c a b c a
i j
a b c a b c a 这边是先remove了 s.charAt(left++) (为第一个a) 然后又判断了一次 把第二个a add到了set 中
i j
a b c a b c a
i j
1 class Solution { 2 public int lengthOfLongestSubstring(String s) { 3 int len = s.length(), res = 0; 4 HashMap<Character, Integer> map = new HashMap<>(); 5 for(int i = 0, j = 0; j < len; j++){ 6 if(map.containsKey(s.charAt(j))){ 7 i = Math.max(map.get(s.charAt(j)),i); 8 } 9 map.put(s.charAt(j), j + 1); //j + 1表示 i要移动的下一个位置 10 res = Math.max(res, j + 1 - i); 11 } 12 return res; 13 } 14 }
方法二 优化
a b c d c c a
a b c d c c a
a b c d c c a这种情况下我们会做无用的移除 可以一步到位跳跃到下一个c的位置 时间复杂度O(N)
a b c d c c a
由于map中的 i 之前的位置没有 remove 所以我们要Math.max ( map.get ( s.charAt ( j ) ) , i ) 确认 i 的坐标不是之前出现的
原文：https://www.cnblogs.com/doomslayer/p/14090746.html