1 题目一 两数之和
题目描述：
给定一个数组nums和一个目标值target,请你在该数组中找出和为目标值的两个整数，并返回他们的下标。你可以假设没中输入只会对应一个答案，但是，你不能重复利用这个数组中同样的元素
实例：
给定 nums = [2,7,11,15],target = 9
因为 nums[0] + nums[1] = 9
所以返回[0，1]
1.1 思路一
看到这个题目，不去想怎么设计，直接的做法是两层循环遍历，检查外层和内层循环对应的数据的值的和是否为target
具体的代码结构如下：
private int[] twoSum1(int[] nums,int target){
for(int i=0;i<nums.length;i++){
for(int j=i;j<nums.length;j++){
if(nums[i] + nums[j] == target){
return new int[]{i,j};
}
}
}
return new int[]{};
}
从上面看，两层循环，时间复杂度是O(n^2)，在内存循环上进行数据的加和校验。然后将对应的下标返回。
1.2 思路二
从上面的算法来看，我初步想要如果要优化，只能将循环的次数减少，时间复杂度降低，只能拿空间换时间。最终的实现逻辑如下：
private int[] twoSum2(int[] nums,int target){
Map<Integer,Integer> maps = new HashMap<Integer, Integer>();
for(int i=0;i<nums.length;i++){
if(maps.containsKey(nums[i])){
return new int[]{maps.get(nums[i]),i};
}
maps.put(target - nums[i],i);
}
return new int[]{};
}
1.3 思路四
参考官方题解，针对思路二，可以采用两次for循环，时间复杂度为O(n)。具体的为：
class Solution {
public 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);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
2 题目二 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
想到的第一种实现方式：
public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
return addTwoNumbers(l1,l2,0);
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2,int carry){
if(l1 == null && l2 == null && carry <= 0){return null;}
int t = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
ListNode l = new ListNode(t % 10);
l.next = addTwoNumbers(l1 == null ? null : l1.next,l2 == null ? null : l2.next,t / 10);
return l;
}
public class ListNode{
int val;
ListNode next;
ListNode(int x) { val = x; }
}
运行结果