Leetcode刷题记录，第一题涉及哈希表，第二题涉及链表，
两数之和
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
1
2
3
| 输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
|
示例 2：
1
2
| 输入：nums = [3,2,4], target = 6
输出：[1,2]
|
示例 3：
1
2
| 输入：nums = [3,3], target = 6
输出：[0,1]
|
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
题目解法
常规解法
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int[] twoSum(int[] nums, int target) {
int length = nums.length;
for(int i = 0;i < length - 1;i++){
for(int j = i + 1;j < length;j++){
if(nums[i] + nums[j] == target){
return new int[]{i,j};
}
}
}
return new int[0];
}
}
|
1.这里注意11行有可能找不到对应的数组下标，此时return new int[0]
new int[0] 是在 Java 中创建一个新的整数数组，但这个数组的长度为0。这意味着这个数组不包含任何元素。虽然这个数组看起来可能没什么用，但在某些情况下，它可以作为一个有效的非空对象返回，以避免返回 null 并可能导致 NullPointerException。这是一种编程技巧，用于处理可能没有数据返回的情况。总的来说，new int[0] 创建了一个空的整数数组。
2.还有7行返回两个数组下标的方法:return new int []{i,j}
3.length是属性，不是方法。直接int length = nums.length即可，无需加括号。
哈希表
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
|
在哈希表中，containsKey方法的平均时间复杂度是O(1)，这意味着无论哈希表的大小如何，查找一个键的时间都是常数。这是因为哈希表使用哈希函数将键映射到一个特定的桶，然后在该桶中查找键，而桶的数量通常是固定的。
然而，这只是平均情况。在最坏的情况下，如果所有的键都哈希到同一个桶，那么查找一个键的时间复杂度将是O(n)，其中n是哈希表中键的数量。但是，如果哈希函数设计得好，并且键的分布是均匀的，那么这种情况是非常罕见的。
所以，当我们说containsKey方法的时间复杂度是O(1)，我们是指在平均情况下。而在你的代码中，你遍历了数组一次，每次调用containsKey方法一次，所以总的时间复杂度是O(n)。
比如输入数组是输入：nums = [2,7,11,15], target = 9
第一步，利用Map<Integer,Integer> hashtable = new HashMap<Integer,Integer>()创建了一个空的HashMap。
第二步，执行循环，当i = 0时，哈希表中显然没有Ke y值为9 - 2 = 7的桶，所以，执行hashtable.put(nums[i],i)，把2当作Key,把·0当作Value放入哈希表。当执行到i = 1时，哈希表中有Key值为9 - 7 = 2的桶（上一步放进去的）。因此直接返回该桶的Value为0,以及这个i为1。所以返回数组return new int[]{ 0 , 1}，符合预期。
两数相加
题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
1
2
3
| 输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
|
示例 2：
1
2
| 输入：l1 = [0], l2 = [0]
输出：[0]
|
示例 3：
1
2
| 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
|
提示：
- 每个链表中的节点数在范围
[1, 100] 内
0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
题目解法
常规解法
主要学习链表相关操作，对链表的处理上模拟正常计算即可
我们这里举例来方便理解，例如342 + 465 = 807，我们在计算时先将2和5相加得到7，可以看到我们这里计算时恰好是逆顺计算的，与给出的逆序链表恰好对应，甚至省去了假如位数不同需要对齐的问题，自动末尾对齐了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
class Solution
{
public ListNode addTwoNumbers(ListNode l1,ListNode l2){
ListNode head = null,tail = null;
int carry = 0;
while(l1 != null || l2 != null){
int n1 = l1 != null ? l1.val:0;
int n2 = l2 != null ? l2.val:0;
int sum = n1 + n2 + carry;
if(head == null){
head = tail = new ListNode(sum % 10);
}else{
tail = tail.next = new ListNode(sum % 10);
}
carry = sum / 10;
if(l1 != null){
l1 = l1.next;
}
if(l2 != null){
l2 = l2.next;
}
}
if(carry > 0){
tail.next = new ListNode(carry);
}
return head;
}
}
|
Debug
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution
{
public ListNode addTwoNumbers(ListNode l1,ListNode l2){
ListNode head = null;
ListNode tail = null;
int carry = 0;
while(l1 != null || l2 != null){
int n1 = l1 != null ? l1.val:0;
int n2 = l2 != null ? l2.val:0;
int sum = n1 + n2 + carry;
if(head == null){
head = tail = new ListNode(sum % 10);
tail = tail.next = null;
}else{
tail = new ListNode(sum % 10);
tail = tail.next = null;
}
carry = sum / 10;
if(l1 != null){
l1 = l1.next;
}
if(l2 != null){
l2 = l2.next;
}
}
if(carry > 0){
tail = new ListNode(carry);
}
return head;
}
}
|
以上这段代码是错误的，原因是 tail是一个指针 ，指向当前链表节点，第13行中tail = tail.next = null;，仅仅会把tail指针置空，而没其他任何效果。因为在tail = new ListNode(val)时，默认tail.next = null，用来默认当前节点是链表的最后一个元素。所以第二次迭代时，仅仅创建了一个没有和任何链表链接的新节点。正确的做法是在创建新节点后，将 tail.next 指向这个新节点，然后再更新 tail 指针指向新的末尾节点。这样，每次迭代时，新创建的节点都会被正确地添加到链表的末尾。 只有创建好新节点，tail.next才能指向新节点
无重复字符的最长子串
题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
1
2
3
| 输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
示例 2:
1
2
3
| 输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
|
示例 3:
1
2
3
4
| 输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
|
提示：
0 <= s.length <= 5 * 104s 由英文字母、数字、符号和空格组成
题目解法
滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution{
public int lengthOfLongestSubstring(String s) {
Set<Character> occ = new HashSet<Character>();
int head = 0,tail = 0,n = s.length(),ans = 0;
for(;head < n;head++){
if(head != 0){
occ.remove(s.charAt(head-1));
}
while(tail < n && !occ.contains(s.charAt(tail))){
occ.add(s.charAt(tail));
tail++;
}
ans = Math.max(ans,tail - head);
}
return ans;
}
}
|
1.注意第 4 行中的length是方法，不是属性。需要int n = s.length()，注意加小括号，这里注意区分两数之和处的int []类型的nums的length是属性，并非方法，无需加括号。
2.还有9行occ.contains(s.charAt(tail))要去找尾巴，别找错了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int lengthOfLongestSubstring(String s) {
int lens = s.length();
if (s==null || s.length()==0){
return 0;
}
int maxLength = 0;
int[] lookup = new int[128];
Arrays.fill(lookup, -1);
int loc = -1;
for (int end = 0;end <lens;end++){
char ch = s.charAt(end);
if (lookup[ch] != -1){
loc = Math.max(loc, lookup[ch]);
}
lookup[ch] = end;
maxLength = Math.max(maxLength, end - loc);
}
return maxLength;
}
}
|