第一次作业

一：两数之和

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解：这个问题我的第一想法就是通过遍历数组的方法来获得两个数，通过两层的for循环声明 i,j两个变量使其和为目标值，接上一个if 的判断即可，不过我的这个方法的效率不高，下面是我的代码。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        target=9;
        nums=new int[]{2,7,11,15};
           for(int i=0;i<nums.length;i++){
               for(int j=0;j<nums.length;j++){
                   if(nums[i]+nums[j]==target&&i!=j){
                       return new int[]{i,j};
                    }
               }
           }
        throw new IllegalArgumentException("No two sum solution");
    }
}

下面是参考答案

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();//通过参列表map的结构获得所需答案的地址
    for (int i = 0; i < nums.length; i++) {//一次遍历
        int complement = target - nums[i];//两者相减的结果即为答案
        if (map.containsKey(complement)) {//在参数里找到这个数
            return new int[] { map.get(complement), i };//返回所获得的值
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

二：两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解：这题主要是两个逆序的集合，里面对应的位置的数相加最后得到一个新的数，我们可以通过一个while的循环来获得每个位置的数，再通过一个carry的进制位数来的到两数相加的一个效果（此carry只能为0或1），最后返回一个我们得到的dummyHead。这题我就是参考答案来写的。

/**
 * 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) {
        ListNode dummyHead = new ListNode(0);//构造一个双向节点
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;//十进制，只为0或1 
        while (p != null || q != null) {//考虑是否存在空集合
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;//判断carry的大小
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {//此处为进制位数1
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;//获得最后的值
    }
}

三：无重复字符的最长字串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解：本题我的第一想法也是通过两次的遍历来获得两个数，确定两个数的位置后通过一个减法运算即可得到字符串的长度。但我没写出来，以下代码也是参考答案写下来的，大佬勿怪！

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //allUnique函数去除重复数
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)//两层循环遍历
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);//得到最长的字符串的长度
        return ans;//返回长度值
    }

    public boolean allUnique(String s, int start, int end) {//确认重复方法
        Set<Character> set = new HashSet<>();//将所有的遍历数放入set中
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;//检查该集合中是否已经包含，包含即为重复
            set.add(ch);
        }
        return true;
    }
}