Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit53da465

Browse files
Update
1 parent080c9cc commit53da465

File tree

4 files changed

+110
-29
lines changed

4 files changed

+110
-29
lines changed

‎README.md

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -414,16 +414,15 @@ int countNodes(TreeNode* root) {
414414
|[0707.设计链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0707.设计链表.md)|链表|中等|**模拟**|
415415
|[1047.删除字符串中的所有相邻重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/1047.删除字符串中的所有相邻重复项.md)|栈|简单|**栈**|
416416
|[剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)|字符串|简单|**双指针**|
417+
|[面试题02.07.链表相交](https://github.com/youngyangyang04/leetcode/blob/master/problems/面试题02.07.链表相交.md)|链表|简单|**模拟**|
417418

418419
持续更新中....
419420

420421
#关于作者
421422

422-
大家好，我是程序员Carl，ACM区域赛铜牌获得者，哈工大计算机硕士毕业，先后在腾讯和百度从事后端技术研发，CSDN博客专家。对算法和C++后端技术有一定的见解，利用工作之余重新刷leetcode。
423+
大家好，我是程序员Carl，ACM 校赛、黑龙江省赛、东北四省赛金牌，和亚洲区域赛铜牌获得者，哈工大计算机硕士毕业，先后在腾讯和百度从事后端技术研发，CSDN博客专家。对算法和C++后端技术有一定的见解，利用工作之余重新刷leetcode。
423424

424-
**加我的微信，备注：组队刷题**， 拉你进刷题群，每天一道经典题目分析，而且题目不是孤立的，每一道题目之间都是有关系的，都是由浅入深一脉相承的，所以学习效果最好是每篇连续着看，也许之前你会某些知识点，但是一直没有把知识点串起来，这里每天一篇文章就会帮你把知识点串起来。
425-
426-
我也花了不少精力来整理我的题解，而且我不会发广告，纯自己学习和分享。 欢迎你的加入！
425+
**加我的微信，备注：组队刷题**， 拉你进刷题群，每天一道经典题目分析，而且题目不是孤立的，每一道题目之间都是有关系的，都是由浅入深一脉相承的，所以学习效果最好是每篇连续着看，也许之前你会某些知识点，但是一直没有把知识点串起来，这里每天一篇文章就会帮你把知识点串起来。我也花了不少精力来整理我的题解，而且我不会在群里发任何广告，纯自己学习和分享。 欢迎你的加入！
427426

428427
<aname="微信"></a>
429428
<imgsrc="https://img-blog.csdnimg.cn/20200712232919673.jpeg"data-img="1"width="175"height="175">

‎problems/0015.三数之和.md

Lines changed: 56 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -1,44 +1,40 @@
1-
##题目地址
1+
#题目地址
22
https://leetcode-cn.com/problems/3sum/
33

4-
##思路
4+
>用哈希表解决了[两数之和](https://mp.weixin.qq.com/s/uVAtjOHSeqymV8FeQbliJQ)，那么三数之和呢？
55
6-
###哈希解法
6+
#第15题. 三数之和
77

8+
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
89

9-
两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。
10-
11-
把符合条件的三元组放进vector中，然后在去去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。
12-
13-
去重的过程不好处理，有很多小细节，如果在面试中很难想到位。
10+
**注意：** 答案中不可以包含重复的三元组。
1411

15-
时间复杂度：O(n^2)，但是运行时间很长，不好做剪枝操作
12+
示例：
1613

17-
###双指针
14+
给定数组 nums =[-1, 0, 1, 2, -1, -4]，
1815

19-
**其实这道题目使用哈希法并不十分合适**，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码，而且是用哈希法 在使用两层for循环的时候，能做的剪枝操作很有限，虽然时间复杂度是O(n^2)，也是可以在leetcode上通过，但是程序的执行时间依然比较长 。
20-
21-
接下来我来介绍另一个解法：双指针法，**这道题目使用双指针法 要比哈希法高效一些**，那么来讲解一下具体实现的思路。
22-
23-
动画效果如下：
16+
满足要求的三元组集合为：
17+
[
18+
[-1, 0, 1],
19+
[-1, -1, 2]
20+
]
2421

25-
<videosrc='../video/15.三数之和.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
2622

27-
拿这个nums数组来举例，首先将数组排序，然后 有一层for循环，i从下表0的地方开始，同时定一个下表left 定义在i+1的位置上，定义下表right 在数组结尾的位置上。
23+
#思路
2824

29-
我们依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i] b = nums[left] c = nums[right]。
25+
##哈希解法
3026

31-
接下来我们如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下表就应该想左移动，这样才能让三数之和小一些。
27+
两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。
3228

33-
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了， left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
29+
把符合条件的三元组放进vector中，然后在去去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。
3430

31+
去重的过程不好处理，有很多小细节，如果在面试中很难想到位。
3532

36-
时间复杂度：O(n^2)
33+
时间复杂度可以做到O(n^2)，但还是比较费时的，因为不好做剪枝操作。
3734

38-
##C++代码
39-
40-
###哈希法代码
35+
大家可以尝试使用哈希法写一写，就知道其困难的程度了。
4136

37+
##哈希法C++代码
4238
```
4339
class Solution {
4440
public:
@@ -75,7 +71,32 @@ public:
7571
}
7672
};
7773
```
78-
###双指针法代码
74+
75+
##双指针
76+
77+
**其实这道题目使用哈希法并不十分合适**，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。
78+
79+
而且使用哈希法 在使用两层for循环的时候，能做的剪枝操作很有限，虽然时间复杂度是O(n^2)，也是可以在leetcode上通过，但是程序的执行时间依然比较长 。
80+
81+
接下来我来介绍另一个解法：双指针法，**这道题目使用双指针法 要比哈希法高效一些**，那么来讲解一下具体实现的思路。
82+
83+
动画效果如下：
84+
85+
<videosrc='../video/15.三数之和.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
86+
87+
拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下表0的地方开始，同时定一个下表left 定义在i+1的位置上，定义下表right 在数组结尾的位置上。
88+
89+
依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i] b = nums[left] c = nums[right]。
90+
91+
接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下表就应该向左移动，这样才能让三数之和小一些。
92+
93+
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
94+
95+
时间复杂度：O(n^2)。
96+
97+
98+
##双指针法C++代码
99+
79100
```
80101
class Solution {
81102
public:
@@ -129,5 +150,15 @@ public:
129150
};
130151
```
131152

153+
#思考题
154+
155+
既然三数之和可以使用双指针法，我们之前讲过的[两数之和](https://mp.weixin.qq.com/s/uVAtjOHSeqymV8FeQbliJQ)，可不可以使用双指针法呢？
156+
157+
如果不能，题意如何更改就可以使用双指针法呢？**大家留言说出自己的想法吧！**
158+
159+
两数之和 就不能使用双指针法，因为[两数之和](https://mp.weixin.qq.com/s/uVAtjOHSeqymV8FeQbliJQ)要求返回的是索引下表， 而双指针法一定要排序，一旦排序之后原数组的索引就被改变了。
160+
161+
如果[两数之和](https://mp.weixin.qq.com/s/uVAtjOHSeqymV8FeQbliJQ)要求返回的是数值的话，就可以使用双指针法了。
162+
132163
>更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
133164
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
##题目地址
2+
https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/
3+
4+
##思路
5+
6+
本来很简洁明了的一道题，让题目描述搞的云里雾里的。
7+
8+
简单来说，就是求两个链表交点节点的**指针**。 这里同学们要注意，交点不是数值相等，而是指针相等。
9+
10+
##C++代码
11+
12+
```
13+
class Solution {
14+
public:
15+
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
16+
ListNode* curA = headA;
17+
ListNode* curB = headB;
18+
int lenA = 0, lenB = 0;
19+
while (curA != NULL) { // 求链表A的长度
20+
lenA++;
21+
curA = curA->next;
22+
}
23+
while (curB != NULL) { // 求链表B的长度
24+
lenB++;
25+
curB = curB->next;
26+
}
27+
curA = headA;
28+
curB = headB;
29+
// 让curA为最长链表的头，lenA为其长度
30+
if (lenB > lenA) {
31+
swap (lenA, lenB);
32+
swap (curA, curB);
33+
}
34+
// 求长度差
35+
int gap = lenA - lenB;
36+
// 让curA和curB在同一起点上（末尾位置对齐）
37+
while (gap--) {
38+
curA = curA->next;
39+
}
40+
// 遍历curA 和 curB，遇到相同则直接返回
41+
while (curA != NULL) {
42+
if (curA == curB) {
43+
return curA;
44+
}
45+
curA = curA->next;
46+
curB = curB->next;
47+
}
48+
return NULL;
49+
}
50+
};
51+
```

‎video/15.三数之和.gif

489 KB
Loading

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp