LeetCode 刷题笔记——day 1
LeetCode 刷题笔记——day 1
1. 两数之和
难度：简单
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
我的答案
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int len = nums.size();
for(int i = 0; i < len - 1; i++) {
for(int j = i + 1; j < len; j++){
if(nums[i] + nums[j] == target) {
vector<int> num = {i, j}; //这里不需要新建一个vector<int>，直接return {i， j}即可。
return num;
}
}
}
vector<int> num; //这里不需要新建一个vector<int>，直接return {}即可。
return num;
}
};- 执行用时: 264 ms
- 内存消耗: 9.9 MB
官方答案
哈希表法
看过题解之后，学会了哈希表法，用Java重新写了一遍代码：
思路：往哈希表中一次插入数组元素-数组索引组成的键值对，同时利用 containsKey 函数判断已有列表中是否存在与当前元素相加为 target 的键，由此可在一次循环以内完成目标。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; i++) {
if(hashMap.containsKey(target - nums[i])) {
return new int[]{hashMap.get(target - nums[i]), i};
}
hashMap.put(nums[i], i);
}
return new int[0];
}
}- 执行用时: 2 ms
- 内存消耗: 38.7 MB
2. 两数相加
难度：中等
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]示例 3：
输入：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- 题目数据保证列表表示的数字不含前导零
我的答案
官方答案
（在自己编写超过80行代码且半小时仍无法通过编译时毅然决然放弃了原来的硬方法，参考了官方题解之后才最终重新编写如下代码，是我配不上第二题了。）
思路 创建两个空指针，一个指向头部，一个跟随程序指向尾部，利用三目运算符提取目标数字且在其一链表提前截止时以 0 赋值（必须加入 if 语句判断，切忌指针继续后移），将得到的数据处理后直接利用已有构造函数创建节点，同时指针跟随后移。最后输出头指针即可。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head = nullptr, *p = nullptr;
int a = 0;
while(l1 || l2) {
int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;
int sum = n1 + n2 + a;
a = sum / 10;
if(!head) {
head = p = new ListNode(sum%10);
} else {
p->next = new ListNode(sum%10);
p = p->next;
}
if(l1) {
l1 = l1->next;
}
if(l2) {
l2 = l2->next;
}
}
if(a > 0) {
p->next = new ListNode(a);
}
return head;
}
};- 执行用时: 36 ms
- 内存消耗: 69.4 MB
拿 Java 练习一遍新学的算法：
思路：Java 没有指针概念，直接创建对象即可，思路同上。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode();
ListNode p = head;
int a = 0;
while(l1 != null || l2 != null) {
int n1 = l1 == null ? 0 : l1.val;
int n2 = l2 == null ? 0 : l2.val;
int sum = n1 + n2 + a;
a = sum / 10;
p.next = new ListNode(sum % 10);
p = p.next;
if(l1 != null) {
l1 = l1.next;
}
if(l2 != null) {
l2 = l2.next;
}
}
if(a > 0) {
p.next = new ListNode(a);
}
return head.next;
}
}- 执行用时：2 ms
- 内存消耗：38.8 MB
总结 第一天，刷了两题。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-11-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号