文章目录

两数之和自己写的代码结果 暴力法代码结果 两数相加错误代码修改后代码 无重复字符的最长子串代码优化的滑动窗口

两数之和

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

自己写的

代码

class Solution { public int[] twoSum(int[] nums, int target) { int[] res = {0,0}; for(int i = 0;i<nums.length;i++){ for(int j =i;j<nums.length;j++){ if(i!=j&&nums[i]+nums[j]==target){ res[0]=i;res[1]=j; } } } return res; } }

结果

成功 显示详情 执行用时 : 118 ms, 在Two Sum的Java提交中击败了6.29% 的用户 内存消耗 : 37 MB, 在Two Sum的Java提交中击败了92.49% 的用户

暴力法

代码

class Solution { public int[] twoSum(int[] nums, int target) { for(int i = 0; i < nums.length; i++){ for(int j = i + 1; j < nums.length; j++){ if(nums[j] == target - nums[i]){ return new int[] {i,j}; } } } throw new IllegalArgumentException("No two sum solution"); } }

结果

显示详情 执行用时 : 37 ms, 在Two Sum的Java提交中击败了53.37% 的用户 内存消耗 : 37.4 MB, 在Two Sum的Java提交中击败了89.24% 的用户

两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

错误代码

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int result = 0; int i = 1; ListNode temp = l1; while(temp != null){ result = result + temp.val * i; temp = temp.next; i = i * 10; } i = 1; temp = l2; while(temp != null){ result += temp.val * i; temp = temp.next; i = i * 10; } i = 10; ListNode l3 = new ListNode(result % 10); ListNode head = l3; while(result / i > 0){ l3.next = new ListNode((result / i) % 10); l3 = l3.next; i = i * 10; } return head; } }

报错，数据各种奇怪，其实这时候就应该猜到是数据溢出的问题。最后发现是int类型无法满足数据需求。修改为long类型也会因为链表定义使用了int保存数字而出现其他错误。

修改后代码

class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode tmp1 = l1, tmp2 = l2, l3 = new ListNode(0); ListNode now = l3; int carry = 0; while(tmp1 != null || tmp2 != null){ if(tmp1 == null){ now.next = new ListNode((tmp2.val + carry) % 10); carry = (tmp2.val + carry) / 10; tmp2 = tmp2.next; } else if(tmp2 == null){ now.next = new ListNode((tmp1.val + carry) % 10); carry = (tmp1.val + carry) / 10; tmp1 = tmp1.next; } else{ now.next = new ListNode((tmp1.val + tmp2.val + carry) % 10); carry = (tmp1.val + tmp2.val + carry) / 10; tmp1 = tmp1.next; tmp2 = tmp2.next; } now = now.next; } if(carry == 1) now.next = new ListNode(1);//加数最大位运算结束，和可能因进位而多一位 return l3.next; } }

成功 显示详情 执行用时 : 8 ms, 在Add Two Numbers的Java提交中击败了98.92% 的用户 内存消耗 : 43.4 MB, 在Add Two Numbers的Java提交中击败了88.80% 的用户

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 示例 2:

输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 示例 3:

输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

代码

class Solution { public int lengthOfLongestSubstring(String s) { int max = 0; int flag = 0;//字符是否出现过 String substr = ""; for(int i = 1; i <= s.length(); i++){ for(int j = 1; j <= substr.length(); j++){ if(s.charAt(i - 1) == substr.charAt(j - 1)){ flag = j; break; } } if(flag == 0){ substr += s.charAt(i - 1); } else{ if(max < substr.length()) max = substr.length(); substr = substr.substring(flag) + s.charAt(i - 1); } flag = 0; } if(max < substr.length()) max = substr.length(); return max; } }

成功 显示详情 执行用时 : 38 ms, 在Longest Substring Without Repeating Characters的Java提交中击败了61.57% 的用户 内存消耗 : 50.7 MB, 在Longest Substring Without Repeating Characters的Java提交中击败了24.13% 的用户

优化的滑动窗口

class Solution { public int lengthOfLongestSubstring(String s) { Map<Character,Integer> map = new HashMap<>(); int n = s.length(); int ans = 0; for(int i = 0,j = 0; j < n; j++){ if(map.containsKey(s.charAt(j))){ i = Math.max(map.get(s.charAt(j)),i); } ans = Math.max(ans, j - i + 1); map.put(s.charAt(j), j + 1); } return ans; } }

成功 显示详情 执行用时 : 30 ms, 在Longest Substring Without Repeating Characters的Java提交中击败了75.15% 的用户 内存消耗 : 39.4 MB, 在Longest Substring Without Repeating Characters的Java提交中击败了81.08% 的用户

这是第一次使用哈希表，就是用键值对的方式存储信息，containsKey搜索表中是否存在指定键，get获取指定键的值，put将新的键值对写入表中。