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) 的算法吗?

思路

  • 标签:哈希映射

  • 这道题本身如果通过暴力遍历的话也是很容易解决的,时间复杂度在 O(n2)O(n2)

  • 由于哈希查找的时间复杂度为 O(1)O(1),所以可以利用哈希容器 map 降低时间复杂度

  • 遍历数组 nums,i 为当前下标,每个值都判断map中是否存在 target-nums[i] 的 key 值

  • 如果存在则找到了两个值,如果不存在则将当前的 (nums[i],i) 存入 map 中,继续遍历直到找到为止

  • 如果最终都没有结果则抛出异常

  • 时间复杂度:$$

代码:

class Solution {public int[] twoSum(int[] nums, int target) {Map map = new HashMap<>();for(int i = 0; i< nums.length; i++) {if(map.containsKey(target - nums[i])) {return new int[] {map.get(target-nums[i]),i};map.put(nums[i], i);throw new IllegalArgumentException("No two sum solution");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

  • 题目数据保证列表表示的数字不含前导零

思路

  • 标签:链表

  • 将两个链表看成是相同长度的进行遍历,如果一个链表较短则在前面补 00,比如 987 + 23 = 987 + 023 = 1010

  • 每一位计算的同时需要考虑上一位的进位问题,而当前位计算结束后同样需要更新进位值

  • 如果两个链表全部遍历完毕后,进位值为 11,则在新链表最前方添加节点 11

  • 小技巧:对于链表问题,返回结果为头结点时,通常需要先初始化一个预先指针 pre,该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值,而且链表构造过程需要指针移动,进而会导致头指针丢失,无法返回结果。

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode root = new ListNode(0);ListNode cursor = root;int carry = 0;while(l1 != null || l2 != null || carry != 0) {int l1Val = l1 != null ? l1.val : 0;int l2Val = l2 != null ? l2.val : 0;int sumVal = l1Val + l2Val + carry;carry = sumVal / 10;ListNode sumNode = new ListNode(sumVal % 10);cursor.next = sumNode;cursor = sumNode;if(l1 != null) l1 = l1.next;if(l2 != null) l2 = l2.next;return root.next;3、无重复字符串【m】

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

示例 1:

输入: s = "abcabcbb"输出: 3解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

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

提示:

  • 0 <= s.length <= 5 * 104

  • s 由英文字母、数字、符号和空格组成

思路

标签:滑动窗口

  • 暴力解法时间复杂度较高,会达到O(n2),故而采取滑动窗口的方法降低时间复杂度

  • 定义一个 map 数据结构存储 (k, v),其中 key 值为字符,value 值为字符位置 +1,加 1 表示从字符位置后一个才开始不重复

  • 我们定义不重复子串的开始位置为 start,结束位置为 end

  • 随着 end 不断遍历向后,会遇到与 [start, end] 区间内字符相同的情况,此时将字符作为 key 值,获取其 value 值,并更新 start,此时 [start, end] 区间内不存在重复字符

  • 无论是否更新 start,都会更新其 map 数据结构和结果 ans。

  • 时间复杂度:O(n)

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

暴力法(头尾指针,逐个匹配)

class Solution {public int lengthOfLongestSubstring(String s) {if(s==null|| s.equals(" ")||s.length()==1){return 1;char[] chars = s.toCharArray();Set temp = new HashSet<>();int max = 0;for(int head = 0;head