* 三数之和(中等题)
给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0
?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
方法代码: class Solution { public static List<List<Integer>> threeSum(int[] nums)
{ List<List<Integer>> result = new ArrayList<>(); int len = nums.length; if(nums
.length < 3) return result; Arrays.sort(nums); for(int i = 0 ; i < len; i++) {
if(nums[i] > 0 ) break; if(i>0 && nums[i] == nums[i-1]) continue; int l = i+1, r
= len -1; while(l < r) { int sum = nums[i] + nums[l] + nums[r]; if(sum == 0) {
result.add(Arrays.asList(nums[i],nums[l],nums[r])); while(l < r && nums[l] ==
nums[l+1]) l++; while(l < r && nums[r] == nums[r-1]) r--; l++; r--; } else if(
sum> 0) r--; else if(sum < 0) l++; } } return result; } }
方法解析:
标签:数组遍历
首先对数组进行排序,排序后固定一个数 nums[i],再使用左右指针指向nums[i]后面的两端,数字分别为nums[l]
和nums[r],计算三个数的和 sum判断是否满足为0,满足则添加进结果集
如果 nums[i]大于0,则三数之和必然无法等于0,结束循环
如果 nums[i] == nums[i−1],则说明该数字重复,会导致结果重复,所以应该跳过
当 sum== 0 时,nums[l] == nums[l+1] 则会导致结果重复,应该跳过,L++
当 sum == 0时,]nums[r] ==nums[r−1] 则会导致结果重复,应该跳过,R–
时间复杂度:O(n^2),n为数组长度

* 最接近的三数之和(中等题)
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target
最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如,给定数组 nums = [-1,2,1,-4], 和 target = 1。
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2)。
方法代码: class Solution { public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums); int len = nums.length; int result = nums[0] + nums[1] +nums[2
]; if(len < 3) return target; if(len == 3) return result; int sum = Math.abs(
target- result); for(int i = 0 ;i < len - 2 ; i++) { int l = i + 1; int r = len
-1; while(l < r) { int ans = nums[i] + nums[l] + nums[r]; if(sum > Math.abs(
target- ans)) { sum = Math.abs(target - ans); result = ans; } if(sum == 0)
return target; if(ans > target) { while(l < r && nums[r] == nums[r-1]) r--; r--;
} else if(ans < target){ while(l < r && nums[l] == nums[l+1]) l++; l++; } } }
return result; } }
方法解析:
标签:排序和双指针
本题目因为要计算三个数,如果靠暴力枚举的话时间复杂度会到 O(n^3),需要降低时间复杂度
首先进行数组排序,时间复杂度 O(nlogn)
在数组 nums 中,进行遍历,每遍历一个值利用其下标i,形成一个固定值 nums[i]
再使用前指针指向 l = i + 1 处,后指针指向 r = nums.length - 1 处,也就是结尾处
根据 ans = nums[i] + nums[l] + nums[r] 的结果,判断 ans 与目标 target 的距离,如果更近则更新结果result
同时判断 ans 与 target 的大小关系,因为数组有序,如果 ans > target 则 r–,如果 sum < target 则 l++,如果
ans == target 则说明距离为 0 直接返回结果,整个遍历过程,固定值为 n 次,双指针为 n 次,时间复杂度为 O(n^2)
总时间复杂度:O(nlogn) + O(n^2) = O(n^2)

* 四数之和(中等题)
给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c
+ d 的值与 target 相等?找出所有满足条件且不重复的四元组。
注意:
答案中不可以包含重复的四元组。
示例:
给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。
满足要求的四元组集合为:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
方法代码: class Solution { public List<List<Integer>> fourSum(int[] nums, int
target) { List<List<Integer>> res = new ArrayList<>(); int len = nums.length; if
(len < 4 || nums == null) return res; Arrays.sort(nums); for(int i = 0 ; i < len
-3 ; i++) { if((nums[i] + nums[len-1] + nums[len-2] + nums[len-3]) < target)
continue; if((nums[i] + nums[i+1] + nums[i+2] + nums[i+3]) > target) continue;
for(int j = len - 1 ; j >= 3; j--) { if(i < j) { int r = j-1; int l = i+1; while
(l < r) { int sum = nums[i] + nums[j] + nums[r] + nums[l]; if(sum == target) {
ArrayList<Integer> s = new ArrayList<>(); s.add(nums[i]); s.add(nums[l]); s.add(
nums[r]); s.add(nums[j]); res.add(s); while(l < r && nums[l] == nums[l + 1]) l++
; while(l < r && nums[r] == nums[r - 1]) r--; l++; r--; } else if(sum > target)
{ while(l < r && nums[r] == nums[r - 1]) r--; r--; } else if (sum < target) {
while(l < r && nums[l] == nums[l + 1]) l++; l++; } } } while(i < j && nums[j] ==
nums[j-1]) j--; } while(i < len-3 && nums[i] == nums[i+1]) i++; } return res; }
}
方法解析:

该题和上题三数之和有点相似,只不过这道题算是用了三个指针吧,先把第一个和最后一个给固定住,然后其余两个根据sum的值来进行调节,之后在移动最后一个指针,再重复上一步,最后与第一个相遇之后,第一个指针再往后移。

* 电话号码的字母组合(中等题)
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例:
输入:“23”
输出:[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
方法代码: class Solution { String[] strs = {" ", "*" , "abc" , "def" , "ghi" ,
"jkl" , "mno" , "pqrs" , "tuv" , "wxyz"} ; List<String> res = new ArrayList<>();
public List<String> letterCombinations(String digits) { if(digits == null ||
digits.length() == 0) return new ArrayList<>(); combination(digits, "", 0);
return res; } void combination(String digits ,String letter, int index ) { if(
index== digits.length()) { res.add(letter); return; } String s = strs[digits.
charAt(index)-'0']; for (int i = 0; i < s.length(); i++) { combination(digits ,
letter+ s.charAt(i) , index+1); } } }
方法解析:

该方法是用递归的方法来进行解决的,每次对letter与新数字所对应的字母依次进行拼接,知道全部数字都遍历过一遍,把最终的得到的letter添加到list集合中。

* 删除链表的倒数第N个节点(中等题)
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
方法代码: /** * Definition for singly-linked list. * public class ListNode { *
int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode first = head;
ListNode second= head; for(int i = 0 ; i < n; i++){ if(first == null){ return
null; } else{ first = first.next; } } if(first == null) return head.next; while(
first.next !=null){ first = first.next; second = second.next; } second.next =
second.next.next; return head; } }
方法解析:

该方法是通过指针的方法,先让第一个指针走n步,然后让第一个和第二个指针同时走,当第一个指针下一个结点为NULL时,那么第二个指针的下一个结点就是倒数第n个结点,进行删除。该题还可用栈来进行解决。

* 有效的括号(中等题)
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”
输出: true
示例 2:
输入: “([)]”
输出: false
方法代码: class Solution { public boolean isValid(String s) { int len = s.length()
; char[] c = s.toCharArray(); char[] stack = new char[len]; int top = -1; for(
int i = 0; i < len ;i++){ if(c[i] == ' ') continue; if(c[i] == '(' || c[i] ==
'{' || c[i] == '[') { stack[++top] = c[i]; continue; } if(c[i] == ')' && (top ==
-1 || stack[top--] != '(')) return false; if(c[i] == '}' && (top == -1 || stack[
top--] != '{')) return false; if(c[i] == ']' && (top == -1 || stack[top--] !=
'[')) return false; } if(top != -1) return false; else return true; } }

方法解析:该方法是利用栈的思想进行解决的,当遇到左括号时,全部压入栈内,遇到右括号时,栈顶为空返回false,不为空栈顶元素出栈,检查出栈元素是否与右括号相匹配,不匹配则返回false,匹配就继续循环,最后退出循环,如果top为-1,则返回true,否则返回false。

技术
©2019-2020 Toolsou All rights reserved,
(精华)2020年6月26日 C#类库 文件读写操作帮助类 程序员与架构师华山论道mybatis系列之返回结果映射SpringBoot 与JPA结合中 JpaRepository 里自定义查询(精华2020年6月2日更新) TypeScript函数详解mybatis-config.xml设置默认值配置iPhone 12售价、配置齐曝光:砍掉64GB、电池2227mAh起步Spark SQL-编程C语言表白练习小程序(适合初学者)华为鸿蒙操作系统有哪些特点和优势?余承东《全场景时代 新体验与新生态》演讲全文