目录
有效三角形个数
题解：
我们都知道想要组成一个三角形需要任意两边之和大于第三边，所以我们首先可以想到一个暴力解法也就是遍历整个数组任意三个数的组合，然后判断是否任意两个数之和大于第三边，但是这样的解放时间复杂度为O(n^3)，严重超时
所以我们要优化方法，其实可以仔细想一想如果最短的两条边之和都大于第三条边，那么者三个数一定可以组成三角形，这样我们就只需要判断一次即可。
所以我们只需要找到三个数中最大的两个即可，如果数组是有序的那么找最大值是不是就容易很多了，所以我们可以先将数组排序然后利用单调性找到，三个数中的最大值，在判断是否能组成三角形。
假如排序后的数组为[2,2,3,4,6,8,9,12]
先固定一个最长边max为12，然后定义两个指针left和right用来指向另外两条边
left指向0下标，right指向max的左边一个下标，然后判断left+right是否大于max。此时会有两种可能行性，1.大于则可以构成三角形，2.小于等于则不能构成三角形
- 如果大于就说明这三个数可以构成三角形，而且因为数组是有序的，left到right之间的任意一个数一定比left指向的数大，既然left+right都比max大那么，left到right之间的任意一个数加上right也一定比max大，换句话说，left到right中任意一个数和right，max都能构成三角形，也就不用再向后判断了，最后让right向左移动一个位置。
- 如果小于等于就说明这三个数不过构成三角形，因为数组有序所以，left到right之间的任意一个数一定比right指向的数小，既然left+right都比max小那么，left到right之间的任意一个数加上left也一定也比max小，换句话说，left到right中任意一个数和left，max都不能构成三角形，也不用再一一判断了，最后让left向右移动一个位置。
当12找完后就继续固定一个次大的数字一次类推遍历数组，最后就能找出所有可以注册三角形的数
class Solution {
public int triangleNumber(int[] nums) {
//排序
Arrays.sort(nums);
int max = nums.length - 1;
//2.利用双指针解决问题
int count = 0;
for (int i = max; i >= 2; --i) {//固定最大的数
int left = 0;
int right = i - 1;
while (left < right) {
if (nums[left] + nums[right] > nums[i]) {
count += (right - left);
right--;
} else {
left++;
}
}
}
return count;
}
}无重复字符的最长子串
题解：
看到这个题我们首先可以想到暴力枚举的方法，定义两个指针left，right依次向后遍历出字符串的所有字串，然后找到不重复的最长子串。
以字符串"a,b,c,d,e,c,d,f"为例
解法1：暴力枚举
- 首先定义left=0，right=0，接着right++不断向右探索，每次探索都要判断right指向的字符是否在前面遇到过。
- 当遇到第二个c时发现在前面出现过，说明此时以第一个a开头的子串(left=0)最长就到第二个c前一个位置。
- 然后让left++，按照刚刚的方法继续开始寻找以第一个b(left = 0)开头的最长字串，以此循环
- 直到当当前已经记录的最长子串的长度，大于当前left距离字符串s末尾时结束(因为之后在探索的子串，最长也就是left到最后一个字符的长度，所以当已经记录的最长字串比s.length-left还大时就不用再向后探索了)
代码(可以跳过)
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.equals("")){
return 0;
}
int maxLen = 0;
int left = 0;
int right = 0;
int gat = 0;
while (maxLen < s.length() - left - 1) {
while (gat < right) {
if (s.charAt(gat) == s.charAt(right)) {
left++;
right = left;
break;
}
gat++;
if ((gat-left) > maxLen) {
maxLen = (gat-left);
}
}
gat = left;
right++;
}
return maxLen+1;
}
}但是这种方法显然时间复杂度很高所以我们需要对算法进行优化。
方法二滑动窗口
先对照上图模拟一下刚刚的方法。//left=0(a)表示此时left指向0位置，指向的字符是a
我们可以使用int数组模拟hash表的方法来判断字符串里是否有重复数字，每个字符的ascll码值都对应数组中的一个位置，当这个字符出现时这个位置的值就加1，如果出现两个这个位置的值就会大于1，我们就知道这个字符出现了两次了。
首先left=0(a),right=0(a)，然后right向后探测，left=0(a),right=1(b)，left=0(a),right=2(c)，left=0(a),right=3(d)，left=0(a),right=4(e)。
当left=0(a),right=5(c)时发现‘c’在前面出现过，所以就让left++，left=2(b),right=5(c)。
此时先不着急让right=left，先分析一下此时最长不重复字串长度是5，如果left++，从left=1(b),right=1(b)开始继续再往后找，最多只能找到right=5(c)的位置因为，当right=5时c一定会出现两次，所以此时如果从left=1(b),right=1(b)向后寻找的话能找到的最长子串一定不会大于5(换句话说只要是从left=2(c)位置之前开始探索一定都不会大于5)
因此我们也就不再向后探索，直接让left到left=2(c)的位置。
那么再分析一下，我们刚刚从left=0(a),right=0(a)位置开始向后探索，直到left=0(a),right=6(c)位置，所以我们此时已经知道在字符串s的[0,5]位置是没有重复字符的，所以此时left=2(c)到right=5(c)也没有重复字符，因此right可以在right=5(c)位置直接向后探索。
根据上述方法我们就可以利用滑动窗口的方法依次向后探索
在int数组中没有出现有大于1的位置则将right指向的字符进入窗口，如果有，就将从left开始到出现重复字符位置之间的字符都出窗口(也就是left=2(c)的位置)。
代码
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] hash = new int[128];//用数组模拟哈希表
int right = 0;
int left = 0;
int ret = 0;
while(right < s.length()){
hash[s.charAt(right)]++;//进入窗口
while(hash[s.charAt(right)] > 1){//判断
hash[s.charAt(left)]--;//出窗口
left++;
}
ret = Math.max(ret,right-left+1);
right++;//让下一个字符进入窗口
}
return ret;
}
}在排序数组中查找元素的第⼀个和最后⼀个位置
看到这道题我们首先想到的肯定是直接遍历，找到target然后定位左右位置，但是这样显然是行不通的，因为题上明确规定要求时间复杂度为O(logN)。所以我们要换个思路，既然是要查找，那么我们就可以想到使用二分查找。
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
//找到区间中点
int mid =left + (right - left + 1) / 2;
//分析情况
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target){
right = mid - 1;
}else{
left = mid + 1;
}
}
return -1;
}
}不过使用一般的二分查找我们只能查找到target并不能确定这个位置是开始还是结束，假如找到target后，向两边查找确定位置的话那么当数组中都是target时，时间复杂度还是为O(N)。所以我们要在这个基础上再分析一下。
先来找起始点
nums = [2,5,7,7,8,8,10,13]，target=8我们以这个数组为例
此时我们将这个数组分成两部分
- 小于target[left,mid-1]
- 大于等于target[mid,right]
条件判断
当每次判断nums[mid]和target的大小情况也只会有这两种
- 当nums[mid] < target时，left = mid + 1
- 当nums[id] >= target时，right = mid
当nums[mid] < target时说明当前判断的位置比我们要找的数小，因为数组是递增的，所以我们要找的target一定再mid位置的右边，因为mid位置元素的已经比target小了，mid左边的只会比target更小。所以此时我们要找的数一定是在区间[mid+1，right]，也就要让left=mid+1;
当nums[mid] >= targe时，说明我们要找的数就在区间[left,mid]中，为什么这里是mid不是mid-1，因为我们要找的是起始点，而且有可能mid位置命中的刚好就是target的起始点。如果命中的刚好是target的起始点的话，再让right=mid-1，right就会越过起始点了区间中就没有等于target的了。
让right=mid就能保证right永远不会越过mid，在我们二分查找的过程中，总会有一次mid命中的是target的起始点，就要让right慢慢向左逼近，不过我们要找的是起始点就相当于找target的最左边，又因为我们把[mid,right]设定为大于等于right的区间，所以我们要找的起始点一定在这个区间，也就不能让right越过mid。当mid命中起始点后，right = mid，因为right现在是起始点target所以此时right位置左边的数一定都小于target。
//mid<target代表mid位置的元素大小小于target
循环条件
一般的二分查找的循环条件是while(left <= right)，但是这里的不行因为当left = right = mid时，就已经结束了，此时找到的位置就是target的起始点，假如还和之前一样的判断，以上面的数组为例。
最后left = right = mid=5，此时left和right相等需要再次循环，而nums[mid] = target=8所以执行right=mid；然后继续判断最后一直这样陷入死循环，所以我们的循环条件应该是while(left<right)
求mid
mid就是right和left的中点，直接(right+left)/2就可以找到，但是这样会有一个问题，假如right和left都非常大那么right+left这个值就有可能会超过int的最大限度，就会导致出错。所以我们可以使用下面两种方法
- left+(right-left)/2
- left+(right-left+1)/2
right-left的长度除以2，就是这一段长度的一半，再加上left就是当前区间的中点，不过这两种方法有一个区别，在区间个数为奇数时都是一样。但是当区间个数为偶数时中间点有两个，
left+(right-left)/2求得的是左边的，left+(right-left+1)/2是右边的，但是这里必须使用left+(right-left)/2。假设查找的最后是以下情况
如果此时mid是左边的话，nums[mid] = target，right = mid，然后right=left退出循环。如果mid在右边nums[mid] = target，right = mid，然后left依然小于right循环继续，然后又执行right = mid陷入死循环。
通过上面的分析我们就可以找到起始点，现在再来找终止点。
方法和起始点一样，不过这里要分为
- 小于等于target[left,mid]
- 大于target[mid+1,right]
和找起始点一样，只不过这里反过来了，结束点就是target的最右边，所以要让当mid命中target时(nums[mid]=target)，left向右逼近但是不能越过这个点，所以就让nums[mid] <= target时，left = mid。
求mid
这里就不能使用left+(right-left)/2了因为，如果mid此时是在左边的点，那么nums[mid]<=target，left = mid，然后计算mid还是在left位置，继续判断nums[mid]<=target，left = mid就陷入死循环了。所以求结束点时要使用left+(right-left+1)/2(当元素个数是偶数时，mid为中间两个点的右边)
判断条件和找起始点时一致
到这里我们的起始点和终止点就都找到了
代码实现
class Solution {
public int findLeft(int[] nums,int target){
int left = 0;
int right = nums.length -1;
while(left < right){
//元素个数为偶数时mid为中间两个点的左边
int mid = left + (right - left)/2;
if(nums[mid] >= target){
right = mid;
}else {
left = mid + 1;
}
}
if(nums[left] == target){
return left;
}
return -1;
}
public int findRight(int[] nums,int target){//求终止点
int left = 0;
int right = nums.length -1;
while(left < right){//判断
//元素个数为偶数时mid为中间两个点的右边
int mid = left + (right - left + 1)/2;
if(nums[mid] > target){
right = mid - 1;
}else {
left = mid;
}
}
if(nums[left] == target){
return left;
}
return -1;
}
public int[] searchRange(int[] nums, int target) {
int [] ret = new int[2];
ret[0] = -1;
ret[1] = -1;
if(nums.length == 0){//判空
return ret;
}
ret[0] = findLeft(nums, target);
ret[1] = findRight(nums, target);
return ret;
}
}