SOURCE

/**
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 
 * 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
 * 你可以按任意顺序返回答案。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/two-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * 利用两层循环 外层控制相减得到的值
 * 内层 以i+1 起始位置进行对比 发现相等即返回
 */
// const twoSum = function (nums, target) {
//     const len = nums.length;
//     const result = [];

//     for (let i = 0; i < len; i++) {
//         let other = target - nums[i];
//         for (let j = i + 1; j < len; j++) {
//             if (nums[j] === other) {
//                 result.push(i, j);
//                 return result;
//             }
//         }
//     }

//     return result;
// };

/**
 * 利用map存储值 
 * 如果发现相减之后存在于map结构中那么就返回序列号i以及map的key
 * 注意要先进行判断 后存储 因为会出现 [3,3] 6这种情况
 */
// const twoSum = (nums, target) => {
//     const len = nums.length;
//     const map = new Map();

//     for (let i = 0; i < len; i++) {
//         if (map.has(target - nums[i])) {
//             return [i, map.get(target - nums[i])];
//         }
//         map.set(nums[i], i);
//     }

//     return [];
// };


/**
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，
 * 并且每个节点只能存储 一位 数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}
/**
 * 其实就是利用两个指针 一个指针指向返回新链表的头部（head）
 * 另一个指针移动将链表串接起来
 * sum = num1 + num2 + carry
 * carry = sum / 10 | 0 
 */
// const addTwoNumbers = function (l1, l2) {
//     let head = null;
//     let tail = null;
//     let carry = 0;

//     while (l1 || l2) {
//         const node1 = l1 ? l1.val : 0;
//         const node2 = l2 ? l2.val : 0;

//         const sum = node1 + node2 + carry;
//         carry = sum / 10 | 0;

//         if (!head) {
//             head = tail = new ListNode(sum % 10);
//         } else {
//             tail.next = new ListNode(sum % 10);
//             tail = tail.next;
//         }
//         if (l1) {
//             l1 = l1.next;
//         }
//         if (l2) {
//             l2 = l2.next;
//         }
//     }
//     if (carry) {
//         tail.next = new ListNode(carry);
//     }

//     return head;
// };

/**
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * 输入: s = "abcabcbb"
 * 输出: 3 
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * @param {string} s
 * @return {number}
 * fn:lengthOfLongestSubstring(s) => number
 */

/**
 * 从左往右数 有重复就更新缓存数组 并进行比较
 * 更新max 并清空缓存
 * 概述：从左到右 缓存统计 是否有重复项 O(n^2)
 */
// const lengthOfLongestSubstring = (s) => {
//     const len = s.length;
//     let tempObj = {};
//     let count = 0;
//     let max = 0;

//     if (len <= 1) {
//         return len;
//     }

//     for (let i = 0; i < len; i++) {
//         for (let j = i; j < len; j++) {
//             if (tempObj[s[j]]) {
//                 if (count > max) {
//                     max = count;
//                 }
//                 count = 0;
//                 tempObj = {};
//                 break;
//             } else {
//                 tempObj[s[j]] = s[j];
//                 count += 1;

//             }
//         }
//     }

//     return max;
// };


/**
 * 思路：因为要获取无重复的字符串所以利用Map结构判定是否重复，
 * 以及利用i指针更新重复的最高索引
 * 概括：Map去重 i更新重复的最大索引 O(n)
 */
// const lengthOfLongestSubstring = (s) => {
//     const len = s.length;
//     const map = new Map();
//     let i = 0;//重复的索引位置
//     let max = 0;

//     for (let j = 0; j < len; j++) {
//         if (map.has(s[j])) {
//             i = Math.max(map.get(s[j]) + 1, i);
//         }
//         map.set(s[j], j);
//         max = Math.max(max, j - i + 1);
//     }

//     return max;
// };