题意是让你从给定的数组中找到两个元素的和为指定值的两个索引，最容易的当然是循环两次，复杂度为`O(n^2)`，首次提交居然是2ms，打败了100%的提交，谜一样的结果，之后再次提交就再也没跑到过2ms了。

classSolution {

publicint[]twoSum(int[]nums,inttarget) {

int st=0, end= nums.length;

利用HashMap作为存储，键为目标值减去当前元素值，索引为值，比如`i = 0`时，此时首先要判断`nums[0] = 2`是否在map中，如果不存在，那么插入键值对`key = 9 - 2 = 7, value = 0`，之后当`i = 1`时，此时判断`nums[1] = 7`已存在于map中，那么取出该`value = 0`作为第一个返回值，当前`i`作为第二个返回值，具体代码如下所示。

classSolution {

publicint[]twoSum(int[]nums,inttarget) {

int len= nums.length;

题意我也是看了好久才看懂，就是以链表表示一个数，低位在前，高位在后，所以题中的例子就是`342 + 465 = 807`，所以我们模拟计算即可。

题意是计算不带重复字符的最长子字符串的长度，开辟一个hash数组来存储该字符上次出现的位置，比如`hash[a] = 3`就是代表`a`字符前一次出现的索引在3，遍历该字符串，获取到上次出现的最大索引（只能向前，不能退后），与当前的索引做差获取的就是本次所需长度，从中迭代出最大值就是最终答案。

classSolution {

publicintlengthOfLongestSubstring(Strings) {

int len;

题意是给你两个已排序的递增数组，让你找出其中位数，乍一看这题并不是很难，其实这题难度不可小觑，要做出时间复杂度为O(log (m+n))的话需要了解从两个递增数组中找出第k大的元素，也就是我写的`helper`函数所起到的作用。下面来解释以下其原理：假设数组分别记为A，B，当前需要搜索第k大的数，于是我们可以考虑从数组A中取出前m个元素，从数组B中取出k-m个元素。由于数组A，B分别排序，则A[m]大于从数组A中取出的其他所有元素，B[k-m] 大于数组B中取出的其他所有元素。此时，尽管取出元素之间的相对大小关系不确定，但A[m]与B[k-m]的较大者一定是这k个元素中最大的。那么，较小的那个元素一定不是第k大的，它至多是第k-1大的：因为它小于其他未被取出的所有元素，并且小于取出的k个元素中最大的那个。为叙述方便，假设A[m]是较小的那个元素。那么，我们可以进一步说，A[1], A[2]…A[m-1]也一定不是第k大的元素，因为它们小于A[m]，而A[m]至多是第k-1大的。因此，我们可以把较小元素所在数组中选出的所有元素统统排除，并且相应地减少k值。这样，我们就完成了一次范围缩小。特别地，我们可以选取m=k/2。而本题只是其一种情况而已，也就当总长为偶数时，找出其中间的两个数，相加除二即可；当总长为奇数时，找到中间的数即可。

classSolution {

publicdoublefindMedianSortedArrays(int[]nums1,int[]nums2) {

int len= nums1.length+ nums2.length;

题意是给你一个整型数，求它的逆序整型数，而且有个小坑点，当它的逆序整型数溢出的话，那么就返回0，用我们代码表示的话可以求得结果保存在long中，最后把结果和整型的两个范围比较即可。

classSolution {

publicintreverse(intx) {

long res=0;

题意是把一个字符串转为整型，但要注意所给的要求，先去除最前面的空格，然后判断正负数，注意正数可能包含`+`，如果之后存在非数字或全为空则返回`0`，而如果合法的值超过int表示的最大范围，则根据正负号返回`INT_MAX`或`INT_MIN`。

classSolution {

publicintmyAtoi(Stringstr) {

int i=0, ans=0, sign=1, len= str.length();

题意是判断一个有符号整型数是否是回文，也就是逆序过来的整数和原整数相同，首先负数肯定不是，接下来我们分析一下最普通的解法，就是直接算出他的回文数，然后和给定值比较即可。

classSolution {

publicbooleanisPalindrome(intx) {

if (x<0)returnfalse;

好好思考下是否需要计算整个长度，比如1234321，其实不然，我们只需要计算一半的长度即可，就是在计算过程中的那个逆序数比不断除10的数大就结束计算即可，但是这也带来了另一个问题，比如10的倍数的数10010，它也会返回`true`，所以我们需要对10的倍数的数再加个判断即可，代码如下所示。

publicboolean isPalindrome(int x) {

if (x<0|| (x!=0&& x%10==0))returnfalse;

int halfReverseX=0;

题意是

classSolution {

publicbooleanisMatch(Strings,Stringp) {

if (p.length()==0)return s.length()==0;

classSolution {

publicbooleanisMatch(Strings,Stringp) {

if (p.length()==0)return s.length()==0;

那么我们可以利用map来完成罗马数字的7个数字符号：I、V、X、L、C、D、M和整数的映射关系，然后根据上面的解释来模拟完成即可。

classSolution {

publicintromanToInt(Strings) {

Map<Character,Integer> map=newHashMap<>();

题意是让你从字符串数组中找出公共前缀，我的想法是找出最短的那个字符串的长度`minLen`，然后在`0...minLen`的范围比较所有字符串，如果比较到有不同的字符，那么直接返回当前索引长度的字符串即可，否则最后返回最短的字符串即可。

classSolution {

publicStringlongestCommonPrefix(String[]strs) {

int len= strs.length;

题意是让你从数组中找出所有三个和为0的元素构成的非重复序列，这样的话我们可以把数组先做下排序，然后遍历这个排序数组，用两个指针分别指向当前元素的下一个和数组尾部，判断三者和与0的大小来移动两个指针，其中细节操作就是注意去重。

classSolution {

publicList<List<Integer>>threeSum(int[]nums) {

Arrays.sort(nums);

题意是给你按键，让你组合出所有不同结果，首先想到的肯定是回溯了，对每个按键的所有情况进行回溯，回溯的终点就是结果字符串长度和按键长度相同。

classSolution {

privatestaticString[] map=newString[]{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

还有一种思路就是利用队列，根据上一次队列中的值，该值拼接当前可选值来不断迭代其结果，具体代码如下。

classSolution {

privatestaticString[] map=newString[]{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

题意是让你删除链表中的倒数第n个数，我的解法是利用双指针，这两个指针相差n个元素，当后面的指针扫到链表末尾的时候，自然它前面的那个指针所指向的下一个元素就是要删除的元素，即`pre.next = pre.next.next;`，但是如果一开始后面的指针指向的为空，此时代表的意思就是要删除第一个元素，即`head = head.next;`。

题意是判断括号匹配是否正确，很明显，我们可以用栈来解决这个问题，当出现左括号的时候入栈，当遇到右括号时，判断栈顶的左括号是否何其匹配，不匹配的话直接返回`false`即可，最终判断是否空栈即可，这里我们可以用数组模拟栈的操作使其操作更快，有个细节注意下`top = 1;`，从而省去了之后判空的操作和`top - 1`导致数组越界的错误。

classSolution {

publicbooleanisValid(Strings) {

char[] stack=newchar[s.length()+1];

题意是用一个新链表来合并两个已排序的链表，那我们只需要从头开始比较已排序的两个链表，新链表指针每次指向值小的节点，依次比较下去，最后，当其中一个链表到达了末尾，我们只需要把新链表指针指向另一个没有到末尾的链表此时的指针即可。

题意是合并多个已排序的链表，分析并描述其复杂度，我们可以用分治法来两两合并他们，假设`k`为总链表个数，`N`为总元素个数，那么其时间复杂度为`O(Nlogk)`。

还有另一种思路是利用优先队列，该数据结构用到的是堆排序，所以对总链表个数为`k`的复杂度为`logk`，总元素为个数为`N`的话，其时间复杂度也为`O(Nlogk)`。

题意是让你从一个有序的数组中移除重复的元素，并返回之后数组的长度。我的思路是判断长度小于等于1的话直接返回原长度即可，否则的话遍历一遍数组，用一个`tail`变量指向尾部，如果后面的元素和前面的元素不同，就让`tail`变量加一，最后返回`tail`即可。

classSolution {

publicintremoveDuplicates(int[]nums) {

int len= nums.length;

题意是移除数组中值等于`val`的元素，并返回之后数组的长度，并且题目中指定空间复杂度为O(1)，我的思路是用`tail`标记尾部，遍历该数组时当索引元素不等于`val`时，`tail`加一，尾部指向当前元素，最后返回`tail`即可。

classSolution {

publicintremoveElement(int[]nums,intval) {

int tail=0;

题意是从主串中找到子串的索引，如果找不到则返回-1，我们只需要遍历主串长度减子串长度即可，利用substring比较即可。

classSolution {

publicintstrStr(Stringhaystack,Stringneedle) {

int l1= haystack.length(), l2= needle.length(), l3= l1- l2;

题意是让你从一个没有重复元素的已排序数组中找到插入位置的索引。因为数组已排序，所以我们可以想到二分查找法，因为查找到的条件是找到第一个等于或者大于`target`的元素的位置，所以二分法略作变动即可。

classSolution {

publicintsearchInsert(int[]nums,inttarget) {

int left=0, right= nums.length-1, mid= (right+ left)>>1;

题意是数和说，根据如下序列`1, 11, 21, 1211, 111221, ...`，求第n个数，规则很简单,就是数和说，数就是数这个数数字有几个，说就是说这个数，所以`1`就是1个1：`11`,`11`就是有2个1：`21`，`21`就是1个2、1个1：`1211`，可想而知后面就是`111221`，思路的话就是按这个逻辑模拟出来即可。

classSolution {

publicStringcountAndSay(intn) {

String str="1";

题意是求数组中子数组的最大和，这种最优问题一般第一时间想到的就是动态规划，我们可以这样想，当部分序列和大于零的话就一直加下一个元素即可，并和当前最大值进行比较，如果出现部分序列小于零的情况，那肯定就是从当前元素算起。其转移方程就是`dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);`，由于我们不需要保留dp状态，故可以优化空间复杂度为1，即`dp = nums[i] + (dp > 0 ? dp : 0);`。

classSolution {

publicintmaxSubArray(int[]nums) {

int len= nums.length, dp= nums[0], max= dp;

题目也给了我们另一种思路，就是分治，所谓分治就是把问题分割成更小的，最后再合并即可，我们把`nums`一分为二先，那么就有两种情况，一种最大序列包括中间的值，一种就是不包括，也就是在左边或者右边；当最大序列在中间的时候那我们就把它两侧的最大和算出即可；当在两侧的话就继续分治即可。

classSolution {

publicintmaxSubArray(int[]nums) {

return helper(nums,0, nums.length-1);

题意是让你从一个只包含大小字母和空格字符的字符串中得到最后一个单词的长度，很简单，我们倒序遍历，先得到最后一个非空格字符的索引，然后再得到它前面的空格字符索引，两者相减即可。当然，我们使用API来完成这件事更加方便，只需一行代码`return s.trim().length() - s.trim().lastIndexOf(" ") - 1;`，但我相信作者出这道题的目的肯定不是考你API的使用，所以我们还是用自己的思路来实现。

classSolution {

publicintlengthOfLastWord(Strings) {

int p= s.length()-1;

题意是给你一个数字数组，高位在前，并且首位不为0除非这个数组就是`[0]`，让你给该数组低位加一求其结果，那么我们就模拟小学数学那样进位去算即可，如果一直进位到首位，这种情况也就是都是由9组成的数组，此时我们只要new出一个多一个长度的数组即可，并把第0个元素赋1即可。

classSolution {

publicint[]plusOne(int[]digits) {

int p= digits.length-1;

题意是给你两个二进制串，求其和的二进制串。我们就按照小学算数那么来做，用`carry`表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。

classSolution {

publicStringaddBinary(Stringa,Stringb) {

StringBuilder sb=newStringBuilder();

题意是求平方根，参考[牛顿迭代法求平方根](https://wenku.baidu.com/view/6b74c622bcd126fff7050bfe.html)，然后再参考维基百科的[Integer square root](https://en.wikipedia.org/wiki/Integer_square_root#Using_only_integer_division)即可。

classSolution {

publicintmySqrt(intx) {

long n= x;

题意是爬楼梯，每次你只能爬一步或者两步，问到顶层共有多少种方案。我们假设到顶层共有`f(n)`种，那么`f(n) = f(n - 1) + f(n - 2)`肯定是成立的，意思就是我们迈向顶层的最后一步是在倒数第一级台阶或者在倒数第二级台阶。算法我对空间复杂度进行了优化，因为在迭代过程中只需要两个变量即可。

classSolution {

publicintclimbStairs(intn) {

int a=1, b=1;

题意是删除链表中重复的元素，很简单，我们只需要遍历一遍链表，遇到链表中相邻元素相同时，把当前指针指向下下个元素即可。

题意是给两个已排序的数组`nums1`和`nums2`，合并`nums2`到`nums1`中，两数组元素个数分别为`m`和`n`，而且`nums1`数组的长度足够容纳`m + n`个元素，如果我们按顺序排下去，那肯定要开辟一个新数组来保存元素，如果我们选择逆序，这样利用`nums1`自身空间足矣，不会出现覆盖的情况，依次把大的元素插入到`nums1`的末尾，确保`nums2`中的元素全部插入到`nums1`即可。

classSolution {

publicvoidmerge(int[]nums1,intm,int[]nums2,intn) {

int p= m--+ n---1;

题意是比较两棵二叉树是否相同，那么我们就深搜比较各个节点即可。

题意是判断一棵二叉树是否左右对称，首先想到的是深搜，比较根结点的左右两棵子树是否对称，如果左右子树的值相同，那么再分别对左子树的左节点和右子树的右节点，左子树的右节点和右子树的左节点做比较即可。

第二种思路就是宽搜了，宽搜肯定要用到队列，Java中可用`LinkedList`替代，也是要做到左子树的左节点和右子树的右节点，左子树的右节点和右子树的左节点做比较即可。

题意是找到二叉树的最大深度，很明显，深搜即可，每深入一次节点加一即可，然后取左右子树的最大深度。