Iterfun's Blog

https://leetcode.cn/problems/3sum/ 题面给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意： 答案中不可以包含重复的三元组。 示例： 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ] 思路① 双指针，时间O(n^2)，空间O(1)12345678910111213141516171819202122232425262728293031323334public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); // 找出 a + b + c = 0 // ...

https://leetcode.cn/problems/ransom-note/ 题面给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。 (题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。) 注意： 你可以假设两个字符串均只含有小写字母。 canConstruct(“a”, “b”) -> falsecanConstruct(“aa”, “ab”) -> falsecanConstruct(“aa”, “aab”) -> true 分析本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成，但是这里需要注意两点。 第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。 第二点 “你可以假设两个字符串均只含有小写字母。” ...

https://leetcode.cn/problems/4sum-ii/ 题面给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。 为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。 例如: 输入: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] 输出: 2 解释: 两个元组如下: (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0 思路：哈希，时间O(n ...

https://leetcode.cn/problems/two-sum/ 题面给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 思路① 暴力，时间O(n^2)，空间O(n^2)思路② 哈希，map，时间O(n)，空间O(n)想清楚map的key和value分别用来存什么——key存数字，value存下标。 12345678910111213141516public int[] twoSum(int[] sums, int target) { int[] res = new int[2]; if (nums == null || nums.length == 0) return res; ...

https://leetcode.cn/problems/happy-number/ 题面编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。 如果 n 是快乐数就返回 True ；不是，则返回 False 。 示例： 输入：19输出：true解释：1^2 + 9^2 = 828^2 + 2^2 = 686^2 + 8^2 = 1001^2 + 0^2 + 0^2 = 1 思路：哈希，时间O(log n)，空间O(log n)题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！（当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。） 还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。 123456789101112131415161718public boolean i ...

https://leetcode.cn/problems/intersection-of-two-arrays/ 题面题意：给定两个数组，编写一个函数来计算它们的交集。 思路① 暴力，时间O(n^2)思路② 哈希，时间O(m+n)，空间O(n)版本一：使用HashSet12345678910111213141516171819202122232425262728public int[] intersection(int[] nums1, int[] nums2) { if (nums1 == null || nums1.length == 0 || nums2 == null || nums.length == 0) { return new int[0]; } Set<Integer> set1 = new HashSet<>(); Set<Integer> resSet = new HashSet<>(); // 遍历数组1 for (int i : nums1) { set1.add(i ...

https://leetcode.cn/problems/valid-anagram/ 题面给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。 注意：若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。 思路① 暴力，两层for，时间O(n^2)思路② 数组+哈希，时间O(n)，空间O(1)123456789101112131415161718public boolean isAnagram(String s, String t) { int[] record = new int[26]; for (int i = 0; i < s.length(); i++) { record[s.chatAt(i) - 'a']++; // 不需要记住字符a的ASCII，求出相对数组就行 } for (int i = 0; i < t.length(); i++) { re ...

https://leetcode.cn/problems/linked-list-cycle-ii/ 题面给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 思路：快慢指针，时间O(n)，空间O(1)主要考察两个知识点： 判断链表是否有环 如果有环，如何找到这个环 判断链表是否有环可以用快慢指针，fast每次走两步，slow每次走一步，如果有环，它们一定会相遇。 如果有环，如何找到这个环已经判断链表有环了，那么接下来要找这个环的入口。 可以用一点数学知识，可以得出等式：2(x+y) = x+y+n(y+z) (n是指慢指针进入环之前，快指针已经在环内跑的圈数)=> x+y = n(y+z)=> x=n(y+z)-y=> x=(n-1)(y+z)+z从上式能看得出y+z是一圈的长度，n-1是代表快指 ...

https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/ 题面给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。 图示两个链表在节点 c1 开始相交： 题目数据 保证 整个链式结构中不存在环。 注意，函数返回结果后，链表必须 保持其原始结构 。 思路① 先行移动长链表实现同步移动注意，是求两个链表交点节点的指针，不是数值相等，而是指针相等。 1234567891011121314151617181920212223242526272829303132333435363738394041public ListNode getIntersectionNode(ListNode headA, ListNode headB) { listNode curA = headA; listNode curB = headB; int lenA = 0, lenB = 0; while (curA != n ...

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/ 题面给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 进阶：你能尝试使用一趟扫描实现吗？ ## 思路① 快慢指针12345678910111213141516171819202122232425public ListNode removeNthFromEnd(ListNode head, int n) { // 新建一个虚拟头节点指向head ListNode dummyNode = new ListNode(0); dummyNode.next = head; // 快慢指针指向虚拟头节点 ListNode fastIndex = dummyNode; ListNode slowIndex = dummyNode; // 只要快慢指针相差 n 个节点即可（也就是走 n+1 步） for (int i = 0; i < n; i++) { fastI ...