--题目导航见页面左上角的悬浮框#目录导航#--
相似题型导航
1.1 twosum两数之和 || 2.2 3Sum三数之和 || 2.3 3Sum Closest最接近的三数之和
-------------------------------------------------------------------------------------------------------------------------------------
2.1 Add Two Numbers俩数相加 ||
一、简单
1.1 twosum两数之和
原题：
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
实例：
给定 nums = [, , , ], target =
因为 nums[] + nums[] = + =
所以返回 [, ]
暴力解法（java）：
复杂度分析：
时间复杂度：O(n²)， 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)的时间。因此时间复杂度为 O(n²)。
空间复杂度：O(1)。
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] index=new int[];
for(int i=;i<nums.length;i++){
for(int j=i+;j<nums.length;j++){
if(target==nums[i]+nums[j]){
index[]=i;
index[]=j;
return index;
}
}
}
return index;
}
}
一遍hashmap法（java）:
复杂度分析：
时间复杂度：O(n)， 我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。
空间复杂度：O(n)， 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。
class Solution {
public int[] twoSum(int[] nums, int target) {
int index[]=new int[2];
HashMap <Integer,Integer> map=new HashMap<>(); //动态申请key,value均为Integer的名为map的HashMap函数类型
for (int i=0;i<nums.length;i++){
if(map.containsKey(target-nums[i])){ //判断map中是否存在key=target-num[i]
index[0]=map.get(target-nums[i]); //若存在则将key对应的value值赋给index
index[1]=i;
return index;
}else{
map.put(nums[i],i); //若不存在，则需要将i对应的数组值赋给map作为key,将i赋给map作为value,之所以反转的原因是前面是map.get(key)
}
}
return index;
}
}
二、中等
2.1 Add Two Numbers两数相加
原题：
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
实例：
输入：( -> -> ) + ( -> -> )
输出： -> ->
原因： + =
解决：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int num=;
ListNode proNode=new ListNode(); //定义链表头
ListNode currentNode=new ListNode(); //定义链表节点接受俩数之和
proNode.next=currentNode; //连接俩个链表节点
do{
int sum=(l1!=null?l1.val:)+(l2!=null?l2.val:)+num; //当俩个链表都不为null时节点与进位相加
num=sum/; //取进位
int result=sum%; //取余数
currentNode.val=result; //将结果填入新链表的节点中
l1=l1!=null?l1.next:l1; //移动参与计算的链表头
l2=l2!=null?l2.next:l2; //移动参与计算的链表头
if(l1!=null||l2!=null||num!=){ //判断俩链表是否为null,之所以使用l1!=null||l2!null而不是&&的原因是：
// 当测试集为[1,8] [0]时，使用&&判断俩链表均不为空会导致长短不同的链表报错，导致结果为[1]
currentNode.next=new ListNode();
currentNode=currentNode.next; //连接俩节点
}
}while(l1!=null||l2!=null||num!=);
return proNode.next; 返回链表
} }
proNode.next=currentNode 单向节点链接
2.2 3Sum三数之和
原题：
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
实例：
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解决：
在2Sum的问题上解决3Sum的问题，选定i=0,i++来依次作为target，k=i+1,k++和j=nums.length-1 ,j-- 在[Ak~Aj]之间判断是否有nums[k]+nums[j]=-nums[i]的集合
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List; class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result=new LinkedList<>();
if(nums!=null&&nums.length>){
Arrays.sort(nums);
for(int i=;i<nums.length-; ){
int j=i+;
int k= nums.length-;
while(j<k){
if (nums[j]+nums[k]==-nums[i]) {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
result.add(list); k--;
j++; //下面while中继续进行-- ++的目的是为了去重
while (k > j && nums[k] == nums[k + ]) {
k--;
}
while (k > j && nums[j] == nums[j - ]) {
j++;
}
} else if (nums[j]+nums[k]<-nums[i]){
j++;
while (k>j&&nums[j]==nums[j-]){
j++;
}
}
else{
k--;
while (k>j&&nums[k]==nums[k+]){
k--;
}
}
}
i++;
while(i<nums.length-&&nums[i]==nums[i-]){
i++;
}
}
}
return result;
}
}
2.3 3Sum Closest最接近的三数之和
原题：
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
实例：
例如，给定数组 nums = [-，，，-], 和 target = . 与 target 最接近的三个数的和为 . (- + + = ).
解决：
与三数之和的解题思路差不多
class Solution {
public int threeSumClosest(int[] nums ,int target){
Arrays.sort(nums);
long minDiff=Long.MAX_VALUE;
int result=;
int diff=;
int sum=;
for (int i=;i<nums.length-;i++){
int j=i+;
int k=nums.length-;
while (j<k){
sum=nums[i]+nums[j]+nums[k];
diff=Math.abs(sum-target);
if (diff==){
return sum;
}if (diff<minDiff){
minDiff=diff;
result=sum;
}if (sum>target){
k--;
}else {
j++;
}
}
}
return result;
}
}
Math.abs(sum-target)表示取sum-target的绝对值。
【持续更新中，欢迎交流讨论】