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

2019年12月15日 3051点热度 0人点赞 1条评论

内容纲要

题目一

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

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

提示：不能自身相加。

测试用例

[2,7,11,15]
9

预期结果

[0,1]

格式模板

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

笔者的代码，仅供参考

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

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

运行时间 400ms-600ms

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

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

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

        public int[] TwoSum(int[] nums, int target)
        {
            int[] a = new int[2];
            System.Collections.Hashtable h = new System.Collections.Hashtable();
            for (int i = 0; i < nums.Length; i++)
            {
                int c = target - nums[i];
                if (h.ContainsKey(c))
                {
                    a[0] = int.Parse(h.ToString()) <= nums[i] ? int.Parse(h.ToString()) : i;
                    a[1] = int.Parse(h.ToString()) > nums[i] ? int.Parse(h.ToString()) : i;
                }
                else if (!h.ContainsKey(nums[i]))
                {
                    h.Add(nums[i], i);
                }
            }
            return a;
        }

抄一下别人的

public class Solution
{
    public int[] TwoSum(int[] nums, int target)
    {
        int[] res = {0, 0};
        int len = nums.Length;
        Dictionary<int, int> dict = new Dictionary<int, int>();
        for (int i = 0; i < len; i++)
        {
            int query = target - nums[i];
            if (dict.ContainsKey(query))
            {
                int min = (i <= dict[query]) ? i : dict[query];
                int max = (i <= dict[query]) ? dict[query] : i;
                return new int[] { min, max };
            }
            else if (!dict.ContainsKey(nums[i]))
            {
                dict.Add(nums[i], i);
            }
        }

        return 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:

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

示例 3:

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

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

测试实例

输入
" "
"au"
"abcabcbb"
"bbbbb"
"pwwkew"
"aab"

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

代码格式模板

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

    }
}

笔者的代码仅供参考

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

public class Solution {
    public int LengthOfLongestSubstring(string s) {
                    if (s == null || s == "")
                return 0;

            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;                       //是否存在重复
                for (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 + 1;
                        b = true;            
                        break;
                    }
                }
                if (b == false)
                    newMax += 1;
            }
            if (newMax > max) max = newMax;
            return max;
    }
}

完整测试代码(控制台)

using System;

namespace ConsoleApp1
{
    public class Testa
    {
        public int LengthOfLongestSubstring(string s)
        {
            if (s == null || s == "")
                return 0;

            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;                       //是否存在重复
                for (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 + 1;      //重新设置区间数
                        b = true;            
                        break;
                    }
                }
                if (b == false)             ////没有重新设置区间数时加1
                    newMax += 1;
            }
            if (newMax > max) max = newMax;
            return max;
        }
    }
    class Program
    {

        static void Main(string[] args)
        {
            Testa t1 = new Testa();                                     //正确结果
            Console.WriteLine(t1.LengthOfLongestSubstring(" "));        //1
            Console.WriteLine(t1.LengthOfLongestSubstring("au"));       //2
            Console.WriteLine(t1.LengthOfLongestSubstring("abcabcbb")); //3
            Console.WriteLine(t1.LengthOfLongestSubstring("bbbbb"));    //1
            Console.WriteLine(t1.LengthOfLongestSubstring("pwwkew"));   //3
            Console.WriteLine(t1.LengthOfLongestSubstring("aab"));      //2
            Console.ReadKey();
        }
    }
}

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

        public int LengthOfLongestSubstring(string s)
        {
            int n = s.Length;
            HashSet<char> set = new HashSet<char>();        //集合
            int ans = 0, start = 0, stop = 0;               //ans为字符串长度，starp区间起点，stop区间终点
            while (start < n && stop < n)
            {
                // try to extend the range [i, j]
                if (!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++]);
                }
            }
            return ans;
        }

完整控制台测试代码

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp2
{
    public class Solution
    {
        public int LengthOfLongestSubstring(string s)
        {
            int n = s.Length;
            HashSet<char> set = new HashSet<char>();        //集合
            int ans = 0, start = 0, stop = 0;               //ans为字符串长度，starp区间起点，stop区间终点
            while (start < n && stop < n)
            {
                // try to extend the range [i, j]
                if (!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++]);
                }
            }
            return ans;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {

            Solution t1 = new Solution();                                     //正确结果
            Console.WriteLine(t1.LengthOfLongestSubstring(" "));        //1
            Console.WriteLine(t1.LengthOfLongestSubstring("au"));       //2
            Console.WriteLine(t1.LengthOfLongestSubstring("abcabcbb")); //3
            Console.WriteLine(t1.LengthOfLongestSubstring("bbbbb"));    //1
            Console.WriteLine(t1.LengthOfLongestSubstring("pwwkew"));   //3
            Console.WriteLine(t1.LengthOfLongestSubstring("aab"));      //2
            Console.ReadKey();
        }
    }
}