1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案

暴力 or HashMap

HashMap<Integer,Integer> k 是 值， v 是数组的下标

哈希查找的时间复杂度为 O(1)，所以可以利用 HashMap降低时间复杂度

遍历当前数组 ， 判断是否存在target-nums[i] 的 key 值

由于不能返回相同的坐标，因此必须先 判断，再 put

1
2
3
4
5
6
7
8
9
public static int[] twoSum(int[]nums,int target){
    Map<Integer,Integer> map=new HashMap<>();
    for(int i=0;i<nums.length;i++){
        map.put(nums[i],i);
        if(map.containsKey(target-nums[i]))
            return new int[]{i,map.get(target-nums[i])};
    }
    return null;
}

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

  • 题目的大概意思就是链表的val 都是逆序的， 并且最后返回的链表也要是逆序的

image-20220725102723575image-20220725102723575

暴力解法

先遍历链表 ，获取val ，用String 存储

然后通过将String 转换成数字相加，然后再利用split方法，得到res 的每个位数的值

—–需要注意的是相加的过程中 ， 用int ， long 都会导致溢出，最后使用BitInteger， 有一个测试用例的长度 有30+

得到每一位的值之后在创建新的链表返回即可；

image-20220725103034375image-20220725103034375

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.math.BigInteger;
/**
 * 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) {
        StringBuffer s1=new StringBuffer("");
        StringBuffer s2=new StringBuffer("");
        // 获取 每一个节点的val
        while(l1!=null){
            s1.append(l1.val);
            l1=l1.next;
        }
        while(l2!=null){
            s2.append(l2.val);
            l2=l2.next;
        }
        s1=s1.reverse();
        s2=s2.reverse();
        BigInteger num1=new BigInteger(s1.toString());
        BigInteger num2=new BigInteger(s2.toString());
        BigInteger value=num1.add(num2);
        StringBuffer v=new StringBuffer(value.toString());
        v.reverse();
        String[] split = v.toString().split("");
        int size=split.length;  // 记录 每一个节点的val
        int cnt=0;
        ListNode head=new ListNode(Integer.parseInt(split[cnt++])); //头结点
        ListNode res=head;
        while(--size>0){ // 创建链表
            head.next=new ListNode(Integer.parseInt(split[cnt++]));
            head=head.next;
        }
        return  res;
    }
}