查找一个字符串中最长的字符串，这个思路就是从左向右找，用i向右找，j标识开始统计的字符。max记录最大长度.如：
Input: "pwwkew"

Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

[1]算法如下，复杂度O(n)

import java.util.HashMap;
import java.util.Map;
class Solution {

    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        Map<Character,Integer> map= new HashMap<Character,Integer>();
        for(int i =0,j=0;i < s.length();i++){
            Character cha = s.charAt(i);
            if(map.containsKey(cha)){
                j = Math.max(j,map.get(cha)+1);
            }
            map.put(cha,i);
            max = Math.max(max,i-j + 1);
        }
        return max;
    }
}

用链表表示10进制的某一位，这样可以计算大数的相加：如
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

[1]思路：遍历链表，保存进位

/**
 * 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 pre= 0;
        
        ListNode r = new ListNode(-1);
        ListNode p0 = r;
        ListNode p_1 = null;
        ListNode p1 = l1;
        ListNode p2 = l2;
        while(p1 != null || p2 != null || pre > 0){
           int v = p1 ==null ? 0 : p1.val;
           v = p2 ==null ? v : v + p2.val;
           v = v + pre;
            pre = v / 10;
           if(p1 != null){
                p1 = p1.next;
           }
           if(p2 != null){
              p2 = p2.next;
           }
          
           p0.val = v % 10;
           p0.next = new ListNode(-1);
           p_1 = p0;
           p0 = p0.next;
            
        }
       p_1.next = null;
       
        return r;
    }
}

已知数组中有两个数的和是一个target，写算法找出这两个数的索引。如nums = [2, 7, 11, 15], target = 9,找出的index是[0, 1]

[1] 算法思路：索引化，类似数据库中的map，找到一个书x，那么寻找target-x是否在数组中。

import java.util.HashMap;
import java.util.Map;
class Solution {
    
    public int[] twoSum(int[] nums, int target) {
        int [] result = new int[2];
        Map<Integer,Integer> map = new HashMap<Integer,Integer>(nums.length);

      for(int j  = 0 ;j < nums.length;j++){
             if(map.containsKey(target-nums[j])){
                        result[1] = j ;
                        result[0] =map.get(target-nums[j]);
                        break;
                    }else{
                          map.put(nums[j] ,j);
                    }
               
         }
        return result;
    }
}

[2] 算法复杂度，O(n)

所谓丑数,就是只含有2、3或5这三个因子的自然数。前三个丑数按照定义分别是2、3和5。数字 60 = 2 2 3 1 5 1 是第25
个丑数。数字 21 = 2 0 3 1 7 1 由于含有因子7,所以不是丑数。前10个丑数如下表:2,3,4,5,6,8,9,10,12,15,如果我们认为 1 = 2 3 0 5 0 也是一个合法的丑数,则1就是第一个丑数。

这道题目来自Richard Bird书中的第一章[1]。现代社会中,有很多服务依赖一种被称为ID的概念。例如身份证就是一种ID,银行账户也是一种ID,电话号码本质上也是一种ID。假设我们使用非负整数作为某个系统的的ID,所有用户都由一个ID唯一确定。任何时间,这个系统中有些ID处在使用中的状态,有些ID则可以用于分配给新用户。现在的问题是,怎样才能找到最小的可分配ID呢?例
如下面的列表记录了当前正在被使用的ID:

[18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6] ---后面称数组A

[1] 暴力实现： brute force---python，从0开始找到第一个不在list内的整数ID

lst = [18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6]
i = 0
while True:
  if i not in lst:
    print i
    break
  i = i + 1

复杂度分析：可以看出这个算法是2维的，就是在遍历i到n的是一维，然后在一维空间再便利是否在list中，对于这种算法，有个简单的复杂度BigO总结：O（n2),即n的平方
[2]空间换时间实现：这里基于一个事实---这个数组A的长度为15，那么1-16这个取值区间的整数一定有一个最小可用ID，否则，数组里面的数字一定是1，2,3，4,5，6...11,12,13,14,15这样的数组。基于这个事实，我们可以初始化一个长度为16的Bool数组B，默认值为false，然后遍历数组A，如果A的值小于16，比如是8，则把数组B中的B[8]标记为True。最后，我们遍历数组B，找到第一个为False的即为最小可用ID。java实现：

    int[] listA = {18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6};
    int blength = listA.length + 1;//加1是利用如果找不到，n+1 就是最小可用ID
    boolean[] listB = new boolean[blength];
    for(int i =0; i< listB.length;i++){
      listB[i] = false;
    }
    for(int j =0;j < listA.length;j++ ){
      if(listA[j] < blength ){
        int a = listA[j];
        listB[a] = true;
      }
    }
    for(int k =0;k < listB.length;k++){
      if(false == listB[k]){
        System.out.print(k);
        break;
      }
    }

进一步优化，使用bit位运算，进一步节省空间和计算步骤,java代码：注意最后一个for不是在上面的for的维度里面，所以不能算n的平方

     int[] listA = {18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6};
         var intSize = Integer.BYTES*8;
         var lenghB = (listA.length + 1)/intSize +1;
         int[] listBit = new int[lenghB];
         
         for(var i = 0;i < listA.length;i ++) {
             var v = listA[i];
             listBit[v / intSize] |= 1 << (v%intSize);//把该位变成1
         }
         for(var j = 0;j < listBit.length;j ++) {
             int v = listBit[j];
             int vv = ~v;//取反
             if(vv ==0) {
                 continue;
             }
            
             for(var k =0;k < intSize ;k++) {//注意这个for不是在上面的for的维度里面，所以不能算n的平方
                 var testKv = 1 <<k;
                 if((testKv & v) ==0) {
                     System.out.print(intSize*j+k);
                     break;
                 }
             }
            
         }

复杂度分析：这个算法随着N的增长是线性的，所以复杂度为O(n)

[3]分治思想division，分治是个很巧妙的思想。首先是分。把一个问题分成N份，然后锁定问题到其中的1/N，然后对1/N再分，缩小为1/N/N;然后是治：当问题已经缩小为不能再分时，分析里面的数字就可以得出结论。这也是为什么分治的复杂度一般为logN，即除以N多少次变成1。比如常见的二分查找。
java代码如下,注意治的最后落点和没有分的时候的落点一样，就是找最后一个元素的下一个id

 int[] listA =  {18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6};
 int arrayStart = 0;
 int arrayEnd = listA.length -1;
 int left =0;
 while(arrayEnd >= arrayStart) {//最后剩余1个元素，也要和middlenum比较
     left = arrayStart;
     int right ;
     int middleNum = (arrayEnd+arrayStart)/2  ;//数组长度的中间值
     for(right = arrayStart; right <= arrayEnd;right++  ) {
         if(listA[right] <= middleNum) {
             //交换
             int temp = listA[left];
             listA[left] = listA[right];
             listA[right] = temp;
             left++;
         }
     }
     //分的思想
     if(left == middleNum +1) {//表示左边的表已经满了，最小ID还在右边,start 就是left,end 不变
        
        arrayStart = left;

     }else {//ID在左边,start不变,end 变成left-1
        arrayEnd = left -1;
     }
     
     
 }
 System.out.print(left);//最小可用ID的xia一个ID，+1,就是最小ID

复杂度分析，外部循环只是内部循环的重入条件，复杂度是O(n + n/2 + n/4 + ...) = O(2n) = O(n)