C# 算法题系列(一)两数之和、无重复字符的最长子串

概述题目一 原题链接 https://leetcode-cn.com/problems/two-sum/ 给定一个整数数组 nums 和一个目标值 target，请 题目一

原题链接 https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2,7,1)">11,1)">15],target = 9因为 nums[0] + nums[1] = 2 + 7 = 所以返回 [0,1)">1]

提示：不能自身相加。

测试用例

[15]9

预期结果

[1]

格式模板

public class Solution {    int[] TwoSum(int[] nums,int target) {　　　　/*　　　　代码　　　　*/        }    }

 

笔者的代码，仅供参考

使用暴力方法，运行时间 700ms-1100ms

 target) {         int [] a = new int[2];            for (int i = 0; i < nums.Length - 1; i++)            {                int j = i + 1; j < nums.Length; j++)                {                    if (nums[i] + nums[j] == target)                    {                        a[0] = i;                        a[1] = j;                    }                }            }            return a;        }    }

运行时间 400ms-600ms

由于使用的是哈希表，所以缺点是键不能相同。

 target) {                     int[] a = ];            System.Collections.Hashtable hashtable = new System.Collections.Hashtable();            for(0; i < nums.Length; i++)            {                hashtable.Add(nums[i],i);            }            int complement = target - nums[i];                if (hashtable.ContainsKey(complement) && int.Parse(hashtable[complement].ToString())!=i)                {                    a[ i;                    a[1] = .Parse(hashtable[complement].ToString());                }            }             a;        }    }

 还是哈希表，缺点是哈希表存储的类型是object，获取值时需要进行转换。

         target)        {            ];            System.Collections.Hashtable h = int c = target -if (h.ContainsKey(c))                {                    a[0] = int.Parse(h[c].ToString()) <= nums[i] ? .Parse(h[c].ToString()) : i;                    a[int.Parse(h[c].ToString()) > nums[i] ? .Parse(h[c].ToString()) : i;                }                else if (!h.ContainsKey(nums[i]))                {                    h.Add(nums[i],i);                }            }             a;        }

抄一下别人的

 Solution{     target)    {        int[] res = {0};        int len = nums.Length;        Dictionary<int,1)">int> dict = new Dictionary<int>();        0; i < len; i++)        {            int query = target - nums[i];             (dict.ContainsKey(query))            {                int min = (i <= dict[query]) ? i : dict[query];                int max = (i <= dict[query]) ? dict[query] : i;                return [] { min,max };            }            dict.ContainsKey(nums[i]))            {                dict.Add(nums[i],i);            }        }         res;    }}--------------------- 作者：Bruce-Yeung 来源：CSDN 原文：https://blog.csdn.net/lzuacm/article/details/80551669 版权声明：本文为博主原创文章，转载请附上博文链接！

 

题目二

原题地址 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 abc"，所以其长度为 3。

示例 2:

输入: bbbbb1解释: 因为无重复字符的最长子串是 b1。

示例 3:

输入: pwwkewwke3。

要注意字符串为空、变量为null、字符串长度 Length = 1 等情况。

测试实例

输入" "auaab"

预期结果分别是 1,2,3,1,2

代码格式模板

public class Solution {    public int LengthOfLongestSubstring(string s) {            }}

 

笔者的代码仅供参考

使用最笨的方式，200ms左右

int LengthOfLongestSubstring(string s) {                    if (s == null || s == "")                return ;            char[] a = s.tochararray();      字符串转为字符数组            int start = 0;                   区间开始位置            int stop = 0;                    区间结束位置            int newMax = 1;                   当前区间数            int max = 1;                     区间最大个数            for (stop = 1; stop < a.Length; stop++)   每次向后移动一位            {                bool b = false;                       是否存在重复                int i = start; i < stop; i++)  检查当前元素在区间是否有相同值                {                    if (a[stop] == a[i])        如果stop+1位在区间找到相同的字符                    {                        char ls = a[stop];                        if (newMax > max) max = newMax;                        start = i + 1;              区间开始位置重置                        newMax = stop - start + ;                        b = true;                                    break;                    }                }                if (b == false)                    newMax += ;            }             newMax;             max;    }}

完整测试代码(控制台)

using System;namespace ConsoleApp1{     Testa    {         s)        {            1;      重新设置区间数                        b = false)             ////没有重新设置区间数时加1                    newMax +=  max;        }    }     Program    {        static voID Main([] args)        {            Testa t1 = new Testa();                                     正确结果            Console.Writeline(t1.LengthOfLongestSubstring("));        1            Console.Writeline(t1.LengthOfLongestSubstring("));       2            Console.Writeline(t1.LengthOfLongestSubstring(")); 3            Console.Writeline(t1.LengthOfLongestSubstring("));    "));   "));      2            Console.ReadKey();        }    }}

 

使用哈希集合，速度更快，100ms-150ms

        int n = s.Length;            HashSet<char> set = new HashSet<char>();        集合            int ans = 0;               ans为字符串长度，starp区间起点，stop区间终点            while (start < n && stop < n)            {                 try to extend the range [i,j]                set.Contains(s[stop]))                {                    set.Add(s[stop++]);                    ans = Math.Max(ans,stop - start);                    或者ans = ans > (stop - start) ? ans : (stop - start)                }                else                {                    set.Remove(s[start++]);                }            }             ans;        }

 

完整控制台测试代码

 System; System.Collections.Generic; System.linq; ConsoleApp2{     Solution    {         ans;        }    }     Program    {        [] args)        {            Solution t1 = new Solution();                                                 Console.ReadKey();        }    }}

 

总结

以上是内存溢出为你收集整理的C# 算法题系列(一) 两数之和、无重复字符的最长子串全部内容，希望文章能够帮你解决C# 算法题系列(一) 两数之和、无重复字符的最长子串所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。