1512. 好数对的数目
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
题目提示：
1
2
| 1 <= nums.length <= 100
1 <= nums[i] <= 100
|
实例1：
1
2
3
| 输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
|
自己思路：
主要条件i< j并且nums[i] == nums[j]，于是我们只需要循环拿出所有的值，和后面比较下就ok了。这样的思路是没有问题的，但是过于麻烦。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int numIdenticalPairs(int[] nums) {
int count=0;
for(int i=0;i< nums.length;i++){
for(int j=i+1;j< nums.length;j++){
if(nums[i]==nums[j]){
count++;
}
}
}
return count;
}
}
|
别人思路：
题目已经限制是100数组，于是创建一个临时的数值
1
| int[] temp = new int[100];
|
创建临时变量
循环nums，把nums每个值当做temp的key，去做加法，我们知道基础int类型数组初始化默认值为0.这样找出nums数组的值对应temp数组里角标对应的++value值；因为100数值限制，所以nums数值要-1。因为第一个不能算数，所以要-1；
总结就是通过数组得角标来进行加1即可。最后取次数-1就是最终答案。
1
2
3
| for(int num:nums){
count+=(++temp[num-1])-1;
}
|
1513. 仅含 1 的子串数
给你一个二进制字符串 s（仅由 ‘0’ 和 ‘1’ 组成的字符串）。
返回所有字符都为 1 的子字符串的数目。
由于答案可能很大，请你将它对 10^9 + 7 取模后返回。
题目提示：
1
2
| s[i] == '0' 或 s[i] == '1'
1 <= s.length <= 10^5
|
实例1：
1
2
3
4
5
6
| 输入：s = "0110111"
输出：9
解释：共有 9 个子字符串仅由 '1' 组成
"1" -> 5 次
"11" -> 3 次
"111" -> 1 次
|
自己思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public int numSub(String s) {
//循环s，首先找出由1组成的字符串为strs，那么1出现的次数为strs.length+strs.length-1从1开始的+数
//1 1
//11 1+2
//111 1+2+3
//1111 1+2+3+4
//11111 1+2+3+4+5
//111111 1+2+3+4+5+6
StringBuilder sb = new StringBuilder();
Long count =0l;
char[] chars = s.toCharArray();
for(int i=0;i< chars.length;i++){
if(chars[i]=='1'){
//如果有1则存入容器
sb.append(chars[i]);
//如果不是最后一位就跳过
if(i!=chars.length-1){
continue;
}
}
//如果没有，判断容器是否为空，否者计算次数，并清空容器
if(sb.length()!=0){
//先把长度加上
//循环计算长度-1的加法
for(int j=1;j<sb.length()+1;j++){
count+=j;
}
sb=new StringBuilder();
}
}
count=count%1000000007;
return count.intValue();
}
}
|
别人思路：
创建一个s.length()大小的数组
1
| int[] temp = new int[s.length()];
|
判断s最后一位是否是1，如果是1则数组最后一位+1
1
2
3
| if(s.charAt(s.length()-1)=='1'){
temp[s.length()-1]++;
}
|
从后往前循环，如果遇到1就取当前循环位置的后面数+1，比如循环到了6位置，那么我们取7位置+1的值，设置到6位置上去；
1
2
3
4
5
| for(int i = s.length()-2;i>=0;i--){
if(s.charAt(i)=='1'){
temp[i]=temp[i+1]++;
}
}
|
循环数组，加起来即可
1
2
3
4
| int count=0;
for(int i:temp){
count+=i;
}
|
解析：我们发现重复的1子串有规律，比如1-》1，11-》1+2,111->1+2+3。所以用数组来计算每个位置为1的关系，比如第一个1，++前面的就是1，第二个又是一个1，那么我们加角标前面的就是1++，就是2.所以最后数组里的数加起来即可。
3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
题目提示【官方】：
1
2
3
4
5
6
7
8
9
| 标签：滑动窗口
暴力解法时间复杂度较高，会达到 O(n^2)O(n
2
)，故而采取滑动窗口的方法降低时间复杂度
定义一个 map 数据结构存储 (k, v)，其中 key 值为字符，value 值为字符位置 +1，加 1 表示从字符位置后一个才开始不重复
我们定义不重复子串的开始位置为 start，结束位置为 end
随着 end 不断遍历向后，会遇到与 [start, end] 区间内字符相同的情况，此时将字符作为 key 值，获取其 value 值，并更新 start，此时 [start, end] 区间内不存在重复字符
无论是否更新 start，都会更新其 map 数据结构和结果 ans。
时间复杂度：O(n)O(n)
|
实例1：
1
2
3
| 输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
自己思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.equals("")){
return 0;
}
if(s.trim().equals("") && s.length()>0){
return 1;
}
int count =0;
int tempCount=0;
Set<Character> temp = new HashSet<>();
for(int i=0; i< s.length(); i++){
Character c = s.charAt(i);
if(!temp.contains(c)){
temp.add(c);
if(i!=s.length()-1){
continue;
}
}
tempCount++;
if(temp.size()>count){
count=temp.size();
}
temp.clear();
i=tempCount;
i--;
}
return count;
}
}
|
别人思路：
